The Colorful Lollipop
What is the least number of colors needed to color each vertex of the graph below such that no two adjacent vertices have the same color?
Note: In graph theory , two vertices are adjacent if they are connected by an edge.
The answer is 6.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Moderator note:
Great! This solution first shows why 6 is the minimum answer, and then verifies that 6 can indeed be achieved.
The problem states "adjacent vertices", not "connected vertices" so the correct answer to the stated problem is 2.
Log in to reply
In graph theory, two vertices are adjacent if they are connected by an edge. Therefore, physically “connected” vertices are indeed “adjacent”, and thus would require a minimum of 6 different colours.
Chromatic number of a graph ⇒ the smallest number of colours needed to colour the vertices of a graph such that
no 2 connected vertices have the same colour
Δ ⇒ the highest degree of a vertex (the highest number
of edges connected to 1 vertex )
By Brook's theorem , the chromatic number of any connected graph is at most Δ , except for complete graphs and cycle graphs in which case the chromatic number is Δ + 1 .
However since this is not a cycle graph but consists of a complete graph (the hexagon) with an extra node outside it with one edge connecting to it, different colours must be used to colour each of the nodes on the hexagon since all the nodes are interconnected. The node outside the hexagon can be coloured with any one of the 5 colours used in the hexagon except the rightmost node (since it is connected to node outside the hexagon). So in this case the chromatic number is the same as a complete hexagonal graph.
Complete Hexagonal graph ⇒ Δ = 5 ⇒ chromatic number = Δ + 1 = 6
So in this case the chromatic number is 6
This argument is wrong as the Graph is non-planar. Hint : Identify a complete subgraph with six vertices and then argue that six colors are necessary as well as sufficient.
Log in to reply
Brook's Theorem doesn't require non-planar. I'm not too sure what your initial comment is referring to.
Log in to reply
For planar graph, we already have the four-color theorem. I was referring to the statement as stated.
Log in to reply
@Abhishek Sinha
–
Were you trying to say:
"Your statement is wrong, since for planar graphs with a vertex that has degree 5, we know by the four color theorem that the chromatic number is at most 4"?
Log in to reply
@Calvin Lin – Yes, something similar. Since, the argument is invoked with the word "planar", that immediately nullifies the argument. Secondly, as you have stated, this is only a sufficient condition, to show the necessary condition, we need to identify the subgraph K 6 .
Log in to reply
@Abhishek Sinha – Oh haha, that explains my confusion. Brook's theorem is actually true of any graph, not just a planar graph. I didn't read the description that Eamon gave, because I knew the theorem already.
Note that you didn't quote the theorem properly. It states that "the chromatic number is at most Δ ". It does not state that "the chromatic number is equal to Δ ".
Log in to reply
Okay, I've edited it now , thanks.
Log in to reply
Note that the statement "However since this is not a cycle graph but consists of a complete graph with an extra node outside it with one edge connecting to it, the chromatic number must be the maximum Δ " does not follow from the theorem. All that we can say is that the chromatic number is not the maximum, which is Δ + 1 .
Log in to reply
@Calvin Lin – I have now changed that statement now to show that 6 is the minimum answer.
This answer is incorrect. The four color theorem proves you need only 4 colors.
Log in to reply
http://mathworld.wolfram.com/Four-ColorTheorem.html
Nevermind. I see my error.
All the six vertex of the graph are interconnected,hence each of them require a separate colour but as the single vertex is connected to only one of the vertex,it can be coloured using any one of the remaining 5 colours.Thus the minimum no. of colours required is 6.
The graph is just K 6 + v 1 , and the added vertex does affect the color scheme, so trivially we will need 6 colors since the rest of the graph is complete.
We can see that the left side of the graph (not counting the single vertex at the right) contains six vertices, of which each two are connected by an edge.
This means that we cannot have less than six colors. If there were less than six colors, by Pigeonhole Principle there would be two vertices out of the six that are colored the same color, so because each two vertices are connected, this would be a contradiction.
Then, it is easy to see that six colors suffice by coloring each vertex on the left side with a different color and the vertex on the right side with any color except the color of its single connected vertex. So, our answer is 6.