Clearly explaining what the chromatic number of a particular graph is
Given the graph below:
I need to find the chromatic number and explain clearly why this is the case.
I know that the chromatic number has to be at least 3 because the chromatic number of a pentagon-shaped graph is 3 (which in a sense is the "base" of this graph). Simply by trying I can tell that the graph needs to have one more colour, thus the chromatic number is 4.
What I'm stuck on is how do I explain clearly/prove that it is in fact 4. There are so many different ways of colouring it so do I really need to explain all of them? How do I do that in the clearest/most systematic way (if that really is the way to go about this)?
$\endgroup$1 Answer
$\begingroup$To prove that the chromatic number is at most $4$, simply exhibit a proper colouring with $4$ colors. I suppose you have already done this.
To prove that the chromatic number is a least $4$ would usually require checking a vast number of cases. This particular graph was cleverly constructed so that a short and simple argument works. Assume for a contradiction that the graph is properly coloured with only $3$ colours. Call the colours red, blue, and green, and assume that the central vertex is green. Thus, there are no green vertices on the inner ring.
For each vertex $v$ on the outer ring there is a vertex $v'$ on the inner ring such that $v$ and $v'$ have the same neighbours on the outer ring. If $v$ is coloured red or blue, leave it alone; but if $v$ is green, recolour $v$ to match the colour of $v'$.
After this recolouring we have a proper colouring of the outer ring with only two colours, red and blue.. This contradicts the fact that $C_5$ has chromatic number $3$.
There is a general construction (due to Jan Mycielski) which takes as input a triangle-free graph of chromatic number $k$ and outputs a triangle-free graph of chromatic number $k+1$. When the input graph is $C_5$, the output is the $11$-point graph in your question.
P.S. Actually, if you take advantage of the rotational symmetry of the graph you asked about, the "brute force" approach is easier than the "clever" argument. Colour the graph from the outside in. To start with, observe that there is only one way to properly colour the $5$-cycle with $3$ colours, up to rotations of the cycle and permutations of the colours. Once the outer ring is coloured, you can quickly see that all $3$ colours must occur on the inner ring, leaving no colour for the central vertex.
P.P.S. The graph in your question is the Grötzsch graph; it is the Mycielskian of $C_5$. The brute force argument works fine for proving that the Grötzsch graph is $4$-chromatic, but you need something like the first argument I gave if you want to prove that the Mycielskian of a $k$-chromatic graph is $(k+1)$-chromatic.
$\endgroup$ 3
