Skip to main content

Chromatic number of K5, Km,n, Cp

Short answer

The chromatic number χ(K5) = 5 because all vertices are adjacent. χ(Km,n) = 2 since each partite set can use one color. For cycle Cp, χ = 2 when p is even, and χ = 3 when p is odd.

What is chromatic number of K5, K(m,n) and C(p) for p ≥ 3? Explain with suitable figure.

The chromatic number χ(G) is the least number of colors that can be assigned to the vertices so that adjacent vertices get different colors.

K₅

Every pair of the 5 vertices is adjacent, so all of them need different colors: χ(K₅) = 5. In general χ(Kₙ) = n.

 colors:  v1=1, v2=2, v3=3, v4=4, v5=5 (pentagon with all diagonals)

K_{m,n} (complete bipartite, m, n ≥ 1)

The vertices split into A (m vertices) and B (n vertices); edges only go between A and B. Give color 1 to all of A and color 2 to all of B. This coloring is proper, and one color is not enough because there is at least one edge. χ(K_{m,n}) = 2.

  A:  a1  a2  a3        all colored 1
       \   |   /
  B:  b1  b2  b3        all colored 2     (shown for K3,3; every a is
                                           joined to every b, 9 edges)

Cycle C_p (p ≥ 3)

  • p even: alternate two colors 1, 2, 1, 2, ..., 1, 2. The last vertex (color 2) meets the first (color 1), so χ = 2.
  • p odd: alternating fails when you come back to the first vertex (the last one would get color 1, the same as the first). A third color is needed for one vertex: χ = 3.
  C5:   v1=1
       /     \
    v5=3     v2=2        C4: 1,2,1,2 around the square
      |       |
    v4=2 --- v3=1
Graphχ
K₅5
K_{m,n}2
C_p, p even2
C_p, p odd3

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →