Coloring a graph
What is the fewest number of colors needed such that no two adjacent vertices are colored the same?
Note : In graph theory , two vertices are adjacent if they share an edge.
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.
6 solutions
Moderator note:
A number of people attempted to apply the Four Color Map Theorem to this problem. First note that even if it applied, it would still need to be justified (as this solution does) that 4 colors are needed and not less.
Second, however, the Four Color Map Theorem doesn't actually apply, because this can't be made into a map! The connections are crossing over each other. If they are not (or the nodes of the graph can be rearranged such that they are not) the graph is called "planar" and can indeed be made into a map. However, it is impossible to make this particular map planar.
The comments to M. Zeidan's attempted solution further down this page (which is flawed for this reason) have two proofs of this.
This is the same reasoning I used. Very nice answer!
https://en.m.wikipedia.org/wiki/Four color theorem The Four Colour Theorem says it all. Similar concept is used in coloring different regions of a map.
Log in to reply
The four colour theorem is for regions of graphs. Imagine the complete graph K 5 which would need 5 colours for a problem like this
To make this analagous to a map colouring problem the edges cannot overlap. This needs to be drawn on a torus to accomplish that: http://mathworld.wolfram.com/TorusColoring.html
the four color theorem only works for planar graphs
Make sense
Please bear with me, this is my first attempt at a proof.
By the four colour theorem, we know that we need a maximum of four colours to colour a region divided into continuous smaller regions. We just need to show that 3 is not a sufficeint number of colours.
To do this consider one of the two central points (the left central point, for example), and let’s argue by contradiction:
Suppose that we can do it using three colours, and assume that this central point is coloured red.
The two left points must be coloured differently (green for the upper left and blue for the lower one) since they share an edge.
The green dot shares an edge with the top point. This point can’t be red since it shares an edge with the red already. So it can only be blue.
The top blue dot shares an edge with the second central dot, this point has to be green because it shares an edge with the red one.
So, in conclusion, the second central point is now coloured green.
By the same process starting with the blue dot on the left, we reach the conclusion that the second central dot is coloured blue.
And thus, we reach a contradiction (since a dot can only be colored using one colour), so three colours are not enough.
We need at least 4 colours, but the four colour theorem states that 4 colours are enough.
So the answer is 4.
Remember to check the conditions in which a theorem applies. The four color theorem only applies to planar graphs. Is this graph planar?
The four color theorem only works for planar graphs. This graph isn't planar.
Log in to reply
It can be re-drawn to be planar, though.
Log in to reply
how do you do that?
Note that this the graph contains a K 4 as a subgraph, hence it is not planar.
Edit: I made a typo. The graph contains a (topological) K 5 .
Log in to reply
@Calvin Lin – K 4 is planar. Did you mean K 5 ?
@Calvin Lin – K4 is planar. The problem is that this graph has a topological K5. (Kuratowski's Theorem.)
If a simple planar graph has f faces, e edges and v vertices, then Euler's Theorem tells us that v − e + f = 2 . Every face will have at least 3 edges to it, and each edge will abut exactly 2 faces. Thus 3 f ≤ 2 e , and hence e ≤ 3 v − 6 .
This simple graph has 1 8 edges and 8 vertices. The only way that e = 3 v − 6 is possible in a simple planar graph is if 3 f = 2 e , so that every face has exactly 3 edges. This graph has plenty of four-sided faces, so it is not planar.
Just make a net of it
I counted the vertices and I tried used the description below even though I didn't really understand it. What's the graph theory? What does adjacent mean? I would rate this problem an 8 because I didn't really understand what it told me to do.
Log in to reply
You can check out the graph theory wiki page to understand the definition of terms that are new to you.
Despite being a non-planar graph and thus ineligible for the four-color theorem, it can still be four-colored as shown below, rendered as a planar graph plus one edge shown in red.
But, isn’t the color 4 sharing edge with the other 4?
Log in to reply
No it isn't. Notice that colour two is between them, so they aren't sharing an edge
Log in to reply
Yes, but there is another edge connecting the two, going around the outside of the 2 that is between them. For a correct solution, permute the 4,1 and 2 at the bottom clockwise.
Diagram should now be correct.
Okay so this might not be the solution you are looking for but may be a good lower bound estimation for a problem of this sort.
Find the biggest Complete Graph that you can find inside the given graph.
What is a complete graph ?
When everynode is connected to every other node by an edge then you can call that a complete graph.
Example for n=4. Let the nodes be A,B,C and D
- A is connected to B,C and D
- B is connected to A,C and D
- C is connected to A,B and D
- D is connected to A,B and C
So the minimum colours required to color a complete graph of size N is in fact N itself. Because if there are N-1 colors, then there are 2 nodes that have the same color and they have to be connected because it is a complete graph.
Coming back to the problem.
Now I dont know if this will give you a definitive answer to any graph. But it is definitely good for finding a lower bound. Maybe someone who is more experienced in graph coloring can take this forward.
I don't believe this would work the blue vertices are in contact with each other as well as the two greens on the bottom. At first I saw that as a solution as well but it wouldn't work.
using C++ can easily solve this problem
If possible how we can solve it by using c++
This is a possible solution for four colors:
In the following diagram, the four colored circles are all touching each other:
Since all four of these circles are touching, they must all be different colors. Therefore, 3 colors will not suffice and 4 is the minimum.