- Asked 4/9
- 2070 Magh · 2+2 marks
Draw K5 and its chromatic number
Short answer
K5 has five vertices each adjacent to all others, so no two can share a color. Therefore the chromatic number is χ(K5) = 5.
Draw the figure for the complete graph with 5 vertices (This is usually denoted by K5). What is the chromatic number of the complete graph K5?
K₅ (complete graph on 5 vertices): 5 vertices, every pair joined, so 10 edges and every vertex has degree 4.
v1
/ | \
v5 --+-- v2 pentagon v1 v2 v3 v4 v5 plus the five
\ \ | / / diagonals v1v3, v1v4, v2v4, v2v5, v3v5
\ \|/ /
v4 --- v3
Edges: v1v2, v1v3, v1v4, v1v5, v2v3, v2v4, v2v5, v3v4, v3v5, v4v5.
Coloring: all five vertices are mutually adjacent, so no two can share a color.
| Vertex | v1 | v2 | v3 | v4 | v5 |
|---|---|---|---|---|---|
| Color | 1 | 2 | 3 | 4 | 5 |
Fewer than 5 colors would give two adjacent vertices the same color. So χ(K₅) = 5.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Draw K6 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×
- Chromatic number of K5, Km,n, Cp · Discrete Structure, chapter 4
- Graph coloring and chromatic number · Discrete Structure, chapter 4 · asked 3×
- Draw K3,4 and its chromatic number · Discrete Structure, chapter 4
- Draw C7, K5, Q3, K3,4 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