---
title: "Draw K5 and its chromatic number"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:draw-k5-chromatic-number"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-k5-chromatic-number
site: BCT Engineering
---

# Draw K5 and its chromatic number

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Magh, 2+2 marks
- Video: [Chromatic number of a Graph in Discrete Mathematics || 5 Solved Examples || DMS || GATE](https://www.youtube.com/watch?v=2KFVnXwbKcs) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-k5-chromatic-number
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

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?

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

## Answer

**K₅ (complete graph on 5 vertices):** 5 vertices, every pair joined, so 10 edges and every vertex has degree 4.

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

## Check yourself

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

1. How many edges does K5 have, and what is the degree of each vertex?
   A. 5 edges, degree 2
   B. 10 edges, degree 4
   C. 20 edges, degree 4
   D. 10 edges, degree 5
   Answer: B. Every pair of 5 vertices is joined: 5C2 = 10 edges. Each vertex is joined to the other 4, so degree 4. (Key point: Edges of K5)

2. Why must every vertex of K5 get a different color?
   A. Every two vertices are adjacent, so no two can share a color
   B. Each vertex has an odd degree
   C. K5 contains an even cycle
   D. K5 is bipartite
   Answer: A. A proper coloring forbids equal colors on adjacent vertices, and in K5 all pairs are adjacent. (Key point: Why all colors differ)

3. What is chi(K5)?
   A. 4
   B. 3
   C. 2
   D. 5
   Answer: D. Five mutually adjacent vertices need 5 distinct colors, and 5 colors suffice, so chi(K5) = 5. (Key point: Chromatic number of K5)

4. By the same reasoning, what is chi(Kn)?
   A. n
   B. n - 1
   C. 2
   D. n/2
   Answer: A. All n vertices of Kn are mutually adjacent, so n colors are needed. (Key point: General rule)

## Close variants set in other exams

- [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×
- [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×
- [Draw K4,5 and C6; chromatic numbers](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k45-c6-chromatic) — Discrete Structure, chapter 4, asked 4×

## Related in Discrete Structure

- [Chromatic number of K5, Km,n, Cp](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Achromatic-number-k5-kmn-cp) — Discrete Structure, chapter 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×
- [Handshaking theorem; even number of odd vertices](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahandshaking-even-odd-degree-proof) — Discrete Structure, chapter 4, asked 3×
- [Complete and bipartite graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Acomplete-and-bipartite-graph) — Discrete Structure, chapter 4