---
title: "Is K3,3 planar?"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:k33-planar"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/k33-planar
site: BCT Engineering
---

# Is K3,3 planar?

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Bhadra, 4+4 marks
- Video: [25 - Planer Non-Planer Graph K5,  K3,3 in Graph Theory](https://www.youtube.com/watch?v=b5h7drdlzZI) — KnowledgeGATE by Sanchit Sir
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/k33-planar
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Is K3,3 graph a planar graph? Explain it with suitable reasons.

## Short answer

K_{3,3} is not planar. It has v=6, e=9, and no triangles. If planar, Euler's formula would give f=5 faces, but 2e=18 < 4f=20, contradiction. Also, e > 2v-4 for triangle-free planar graphs. By Kuratowski's theorem, it contains a subdivision of itself, so non-planar.

## Answer

#### Planar graph
A graph is **planar** if it can be drawn in the plane without any two edges crossing (edges meet only at vertices).

#### K₃,₃ is not planar
K₃,₃ has two sets of 3 vertices with all 9 edges between them (the "three houses, three utilities" problem). It has v = 6, e = 9, and no triangles (it is bipartite, so there are no odd cycles).

```text
   u1   u2   u3
    |\ /| \ /|        every u is joined
    | X | / \|        to every w (9 edges)
   w1   w2   w3
```

**Reason 1 (Euler's formula).** Suppose K₃,₃ were planar. Then v − e + f = 2 gives f = 2 − 6 + 9 = 5 faces. Every face is bounded by a closed walk of at least 4 edges (no triangles), and every edge borders at most two faces, so 2e ≥ 4f. But 2e = 18 and 4f = 20, so 18 ≥ 20, a contradiction.

**Reason 2 (edge bound).** A simple connected planar graph with no triangles satisfies e ≤ 2v − 4. For K₃,₃: 2v − 4 = 8, but e = 9 > 8.

**Reason 3 (Kuratowski's theorem).** A graph is planar if and only if it has no subgraph that is a subdivision of K₅ or K₃,₃. K₃,₃ is itself K₃,₃, so it is non-planar.

Hence K₃,₃ is **not planar**. (K₃,₂ and K₂,ₙ are planar, but K₃,₃ is the smallest non-planar bipartite graph.)

## Check yourself

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

1. Is K3,3 planar?
   A. Yes
   B. Yes, if drawn carefully
   C. Only after removing one vertex
   D. No
   Answer: D. Several arguments show it cannot be drawn without crossings. (Key point: Verdict)

2. If K3,3 (v = 6, e = 9) were planar, Euler's formula would give f =
   A. 5
   B. 4
   C. 6
   D. 3
   Answer: A. f = 2 - 6 + 9 = 5. (Key point: Face count)

3. What contradiction arises with 2e >= 4f?
   A. 18 >= 12 is false
   B. 18 >= 20 is false
   C. 9 >= 20 is false
   D. 20 >= 18 is false
   Answer: B. Faces need at least 4 edges each since there are no triangles; 2e = 18 but 4f = 20. (Key point: Contradiction)

4. Why does e <= 2v - 4 fail for K3,3?
   A. 2v - 4 = 10 but e = 9
   B. e = 6
   C. 2v - 4 = 8 but e = 9
   D. K3,3 has triangles
   Answer: C. A triangle-free planar graph has at most 2v - 4 edges. (Key point: Edge bound)

## Related in Discrete Structure

- [Short note: Planar graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aplanar-graph-short-note) — 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×
- [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 its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-chromatic-number) — Discrete Structure, chapter 4