---
title: "Draw K4,5 and C6; chromatic numbers"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:draw-k45-c6-chromatic"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-k45-c6-chromatic
site: BCT Engineering
---

# Draw K4,5 and C6; chromatic numbers

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2069 Bhadra, 2+2+2+2 marks
- Video: [Complete Bipartite Graph | Types of graph | Discrete Mathematics](https://www.youtube.com/watch?v=ye7LYc4Hims) — Sandeep Kumar Gour
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-k45-c6-chromatic
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Draw the figure for the complete bipartite graph K4,5 and the cycle graph with 6 vertices (This is usually denoted by C6). What is the chromatic number of the drawn complete bipartite graph K4,5 and the cycle graph C6.

## Short answer

K4,5 is a complete bipartite graph with partitions of sizes 4 and 5. Its chromatic number is 2. C6 is an even cycle of length 6, which is bipartite, so its chromatic number is 2.

## Answer

#### Complete bipartite graph K₄,₅
**K₄,₅ (complete bipartite graph):** A = {a1, a2, a3, a4}, B = {b1, b2, b3, b4, b5}; each of the 4 vertices of A is joined to each of the 5 vertices of B, giving 20 edges.

```text
   a1      a2      a3      a4         set A
   | \ \ \ / | \ \ \ ... (every a joined to every b)
   b1    b2    b3    b4    b5         set B
```

| Edge present? | b1 | b2 | b3 | b4 | b5 |
|---|---|---|---|---|---|
| a1..a4 | yes | yes | yes | yes | yes |

**Coloring:** color 1 for all of A, color 2 for all of B. The graph has edges, so one color is not enough. **χ(K₄,₅) = 2.**

#### Cycle C₆
**C₆ (cycle with 6 vertices):** v1..v6 with edges v1v2, v2v3, v3v4, v4v5, v5v6, v6v1.

```text
        v1
       /  \
     v6    v2
      |    |
     v5    v3
       \  /
        v4
```

**Coloring:** alternate two colors around the cycle.

| Vertex | v1 | v2 | v3 | v4 | v5 | v6 |
|---|---|---|---|---|---|---|
| Color | 1 | 2 | 1 | 2 | 1 | 2 |

v6 (color 2) is adjacent to v5 (1) and v1 (1), so it is proper. One color is not enough. **χ(C₆) = 2** (even cycle).

**Summary:** χ(K₄,₅) = 2 and χ(C₆) = 2.

## Check yourself

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

1. How many edges does K4,5 have?
   A. 9
   B. 20
   C. 10
   D. 16
   Answer: B. Each of 4 vertices in A joins all 5 in B: 4 x 5 = 20. (Key point: Edges of K4,5)

2. What is chi(K4,5)?
   A. 2
   B. 4
   C. 5
   D. 9
   Answer: A. A all color 1 and B all color 2 is proper, and edges force at least 2. (Key point: chi(K4,5))

3. Why can C6 be colored with only 2 colors?
   A. It has no edges
   B. It is an even cycle, so alternating colors close up consistently
   C. It has 6 colors available
   D. It is complete
   Answer: B. With 6 vertices, v6 gets color 2 and meets v5 (1) and v1 (1), so the pattern closes properly. (Key point: Even cycle)

4. Which statement about chi of cycles matches the answers?
   A. Odd cycles need 2 and even cycles need 3
   B. All cycles need 3
   C. Even cycles need 2 colors, odd cycles need 3
   D. chi equals the number of vertices
   Answer: C. C6 (even) has chi = 2, while odd cycles such as C5 and C7 have chi = 3. (Key point: Contrast with C5)

## Close variants set in other exams

- [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 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 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×

## Related in Discrete Structure

- [Complete and bipartite graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Acomplete-and-bipartite-graph) — 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
- [Define bipartite graph with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adefine-bipartite-graph-example) — 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×
- [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