---
title: "Chromatic number of K5, Km,n, Cp"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:chromatic-number-k5-kmn-cp"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/chromatic-number-k5-kmn-cp
site: BCT Engineering
---

# Chromatic number of K5, Km,n, Cp

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2075 Bhadra, 5 marks
- Video: [Vertex Colorings and the Chromatic Number of Graphs | Graph Theory](https://www.youtube.com/watch?v=3VeQhNF5-rE) — Wrath of Math
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/chromatic-number-k5-kmn-cp
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

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

## 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.

## Answer

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.

```text
 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.**

```text
  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**.

```text
  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 even | 2 |
| C_p, p odd | 3 |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. chi(K5) is:
   A. 5
   B. 4
   C. 2
   D. 3
   Answer: A. All 5 vertices are mutually adjacent. (Key point: K5)

2. chi(K(m,n)) is 2 because:
   A. It has m + n vertices
   B. Color all of A with 1 and all of B with 2
   C. Every vertex is adjacent to all others
   D. It has a triangle
   Answer: B. Edges go only between A and B. (Key point: K(m,n))

3. chi of an even cycle is 2 because:
   A. It has a triangle
   B. Alternating fails at the end
   C. Alternating two colors closes up properly
   D. It is complete
   Answer: C. The last vertex gets the second color, differing from the first. (Key point: Even cycle)

4. For odd p, chi(Cp) = 3 because:
   A. The graph is complete
   B. It has an even number of vertices
   C. Each vertex has degree 3
   D. Alternating colors makes the last vertex match the first, so a third is needed
   Answer: D. One vertex needs a third color. (Key point: Odd cycle)

## Related in Discrete Structure

- [Draw K5 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k5-chromatic-number) — Discrete Structure, chapter 4, asked 4×
- [Draw K6 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k6-chromatic-number) — Discrete Structure, chapter 4, asked 4×
- [Graph coloring and chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adefine-graph-coloring-chromatic-number) — Discrete Structure, chapter 4, asked 3×
- [Draw K3,4 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-chromatic-number) — Discrete Structure, chapter 4
- [Draw C7, K5, Q3, K3,4 and color them](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-c7-k5-q3-k34-coloring) — Discrete Structure, chapter 4, asked 2×
- [Draw K3,4 and C5; chromatic numbers](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-c5-chromatic) — Discrete Structure, chapter 4, asked 4×