Asked 4/9
2071 Bhadra · 2+2 marks

Draw K6 and its chromatic number

Short answer

K6 has six vertices all pairwise adjacent, so six different colors are needed. No two vertices can share a color, giving a chromatic number χ(K6) = 6.

Draw the figure for the complete graph with 6 vertices (This is usually denoted by K6). What is the chromatic number of the complete graph K6?

K₆ (complete graph on 6 vertices): 6 vertices, every pair joined, so 15 edges and every vertex has degree 5.

            v1
          /    \
        v6      v2        hexagon v1..v6 plus all 9 diagonals:
        | \    / |        v1v3 v1v4 v1v5 v2v4 v2v5 v2v6
        |  X  X  |        v3v5 v3v6 v4v6
        v5      v3
          \    /
            v4

Edges: all pairs vi vj with 1 ≤ i < j ≤ 6.

Coloring: each vertex is adjacent to all five others, so six different colors are needed.

Vertex	v1	v2	v3	v4	v5	v6
Color	1	2	3	4	5	6

Six colors are enough and fewer cannot work. So χ(K₆) = 6. In general χ(Kₙ) = n.

✓ Answer checked by Claude Opus 5.5 (high effort)

Draw K5 and its chromatic number · Discrete Structure, chapter 4 · asked 4×
Draw K3,4 and C5; chromatic numbers · Discrete Structure, chapter 4 · asked 4×
Draw K4,5 and C6; chromatic numbers · Discrete Structure, chapter 4 · asked 4×
Graph coloring and chromatic number · Discrete Structure, chapter 4 · asked 3×
Draw K3,4 and its chromatic number · Discrete Structure, chapter 4
Draw W6, K6, Q3, K2,5 and color them · Discrete Structure, chapter 4 · asked 2×
Handshaking theorem; even number of odd vertices · Discrete Structure, chapter 4 · asked 3×
Complete and bipartite graph · Discrete Structure, chapter 4
Chromatic number of K5, Km,n, Cp · Discrete Structure, chapter 4

All Discrete Structure chapter 4 questions →

Draw K6 and its chromatic number

Related questions