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

# Draw K3,4 and its chromatic number

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2074 Bhadra, 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-k34-chromatic-number
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Draw the figure for the complete bipartite graph K3,4 and determine its chromatic number.

## Short answer

K3,4 is a complete bipartite graph. Assign one color to all three vertices in set A and another color to the four vertices in set B; no adjacent vertices share a color. Thus χ(K3,4) = 2.

## Answer

**K₃,₄ (complete bipartite graph):** vertex sets A = {a1, a2, a3} and B = {b1, b2, b3, b4}; every vertex of A is joined to every vertex of B, giving 3 × 4 = 12 edges, and no edge inside A or inside B.

```text
   a1       a2       a3        set A
   |\ \    /|\ \    / | \
   | \ \  / | \ \  /  |  \    every a is joined
   |  \ \/  |  \ \/   |   \   to every b
   b1   b2      b3        b4   set B
```
(each of a1, a2, a3 has 4 lines going to b1, b2, b3, b4.)

| Edge present? | b1 | b2 | b3 | b4 |
|---|---|---|---|---|
| a1 | yes | yes | yes | yes |
| a2 | yes | yes | yes | yes |
| a3 | yes | yes | yes | yes |

**Coloring:** give color 1 to all of A and color 2 to all of B. No edge joins two vertices of the same set, so the coloring is proper. One color is not enough because the graph has edges. So **χ(K₃,₄) = 2**. (In general χ(K_{m,n}) = 2.)

## Check yourself

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

1. How many edges does K3,4 have, and where do they lie?
   A. 12 edges, all between A and B only
   B. 12 edges, including edges inside A
   C. 7 edges, one per vertex
   D. 6 edges, between A and B
   Answer: A. 3 x 4 = 12 edges, each joining a vertex of A to one of B; none inside a set. (Key point: Edges of K3,4)

2. Why is giving color 1 to all of A and color 2 to all of B proper?
   A. Every vertex has the same degree
   B. No edge joins two vertices of the same set
   C. A has fewer vertices than B
   D. Colors 1 and 2 are the smallest numbers
   Answer: B. Edges only go between A and B, so endpoints always get different colors. (Key point: Valid coloring)

3. Why is one color not enough for K3,4?
   A. It is not connected
   B. It contains an odd cycle
   C. The graph has edges, whose endpoints need different colors
   D. It has more than 6 vertices
   Answer: C. Any edge forces two different colors, so chi >= 2; with the 2-coloring, chi = 2. (Key point: Lower bound)

4. In general, chi(K_m,n) equals
   A. m + n
   B. max(m, n)
   C. m x n
   D. 2
   Answer: D. Every complete bipartite graph is 2-colorable by sets, and has an edge, so chi = 2. (Key point: General result)

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