In this page, let us prove chromatic number of a cycle with n vertices is 2 if n even and 3 if n odd. Before proving this, let us recall the definition of the chromatic number of a graph.

Chromatic Number of a Graph

Definition: The chromatic number of a graph is the minimum number of colours required to colour the vertices of the graph such that no two adjacent vertices share the same colour.

The chromatic number of a graph G is denoted by 𝜒⁡(𝐺).

Chromatic Number of a Cycle

Theorem: Show that the chromatic number of a cycle with n vertices is 2 if n is even and 3 if n is odd.

Proof:

Let C_n be a cycle graph of n vertices, say v₁, v₂, …, v_n. Lets colours the vertices as follows: v₁ red, v₂ blue, v₃ red, v₄ blue, …, i.e., v_i red when i odd and v_i blue when i even.

This way when n is even, adjacent vertices get the different colours. Also, v_n (n even) and v₁ get the different colours. So the minimum number of colours required to colour all the vertices is 2. Hence, 𝜒⁡(C_n) = 2.

Next assume n is odd. In this case, we colour as follows: v₁ red, v₂ blue, v₃ red, v₄ blue, …

As n is odd, both v₁ and v_n get the same colour, but they are adjacent to each other, a contradiction. Thus, 𝜒⁡(C_n) ≥ 3.

Observe that alternate red/blue colouring is not a problem along the path v₁ → v_n-1. So the last vertex v_n can be coloured using some other colour, say green. So 𝜒⁡(C_n) ≤ 3. Therefore, we conclude that 𝜒⁡(C_n) = 3.

This completes the proof of the theorem.

Also Study:

1. Degree of a Vertex in Graph: Definition, Examples, Handshaking Theorem
2. Simple Graph has Two Vertices of Same Degree: proof
3. Prove that a tree with n vertices has (n-1) edges
4. Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges
5. Chromatic number of a complete graph with n vertices is n: Proof