---
title: "Short note: Planar graph"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:planar-graph-short-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/planar-graph-short-note
site: BCT Engineering
---

# Short note: Planar graph

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2075 Bhadra, 4 marks; 2074 Bhadra, 2 marks (asked 2 times)
- Video: [Graph Theory: 57. Planar Graphs](https://www.youtube.com/watch?v=wnYtITkWAYA) — Sarada Herke
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/planar-graph-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on planar graph (define planar graph with suitable example).

## Short answer

A planar graph can be drawn in the plane with no crossing edges. Example: K4 is planar. Euler's formula: v−e+f=2. For simple planar graphs with v≥3, e≤3v−6. Kuratowski's theorem: a graph is planar iff it contains no subdivision of K5 or K3,3.

## Answer

A graph is **planar** if it can be drawn in the plane so that no two edges cross except at their end vertices. Such a drawing is a *planar embedding*; it divides the plane into regions (faces), including the outer one.

**Example:** K₄ looks non-planar when drawn with two crossing diagonals of a square, but redrawing one diagonal outside the square (or placing a vertex inside a triangle) removes the crossing, so K₄ is planar. All trees and cycles are planar.

```text
          a
         / \
        /   \
       /  d  \       d lies inside triangle abc and
      / /   \ \      is joined to a, b and c
     b --------- c
```

**Results:**
- **Euler's formula:** for a connected planar graph with v vertices, e edges, f faces: v − e + f = 2.
- For a simple connected planar graph with v ≥ 3: e ≤ 3v − 6. If it has no triangles, e ≤ 2v − 4.
- **Kuratowski's theorem:** a graph is planar if and only if it has no subgraph that is a subdivision of K₅ or K₃,₃.
- K₅ (e = 10 > 3·5 − 6 = 9) and K₃,₃ are non-planar.
- Every planar graph can be colored with 4 colors.

Applications: circuit board and VLSI layout, road maps.

## Check yourself

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

1. A graph is planar if:
   A. It has no cycles
   B. Every vertex has degree <= 3
   C. It can be drawn in the plane with no edge crossings
   D. It is a tree
   Answer: C. Edges may meet only at their end vertices. (Key point: Definition)

2. For a connected planar graph, Euler's formula is:
   A. v + e - f = 2
   B. v - e - f = 2
   C. v + e + f = 2
   D. v - e + f = 2
   Answer: D. Vertices minus edges plus faces equals 2. (Key point: Euler's formula)

3. For K5, why does the bound e <= 3v - 6 show it is non-planar?
   A. e = 10 exceeds 3(5) - 6 = 9
   B. e = 9 exceeds 10
   C. e = 5 is too small
   D. Its faces are all triangles
   Answer: A. A planar graph with v = 5 could have at most 9 edges, but K5 has 10. (Key point: Edge bound)

4. Kuratowski's theorem says a graph is planar iff it:
   A. Contains K5
   B. Has no subgraph that is a subdivision of K5 or K3,3
   C. Contains K4
   D. Has no cycles
   Answer: B. Subdivisions of K5 or K3,3 are exactly the obstruction to planarity. (Key point: Kuratowski)

## Related in Discrete Structure

- [Is K3,3 planar?](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ak33-planar) — Discrete Structure, chapter 4