PGDDSA Study · Semester 1

Core Titles

Key headlines and terms for quick recall

Planar graph — drawable in the plane without edge crossings
Plane graph (a specific embedding)
Region / Face — including unbounded outer face
Euler's formula $V - E + F = 2$ for connected planar graphs
$E \le 3V - 6$ for simple planar graphs, $V \ge 3$
$K_5$ and $K_{3,3}$ are non-planar
Kuratowski's theorem, Wagner's theorem

Basic Idea

What it is, why it matters, how it works

What is a planar graph?

A graph is planar if it can be drawn in the plane so that no two edges cross. Such a drawing is a plane embedding, dividing the plane into regions (faces) including one unbounded outer face.

Euler's formula

For any connected planar graph: $V - E + F = 2$ where $V$ = vertices, $E$ = edges, $F$ = faces.

Edge bound

For a simple connected planar graph with $V \ge 3$ : $E \le 3V - 6$ This follows because every face is bounded by at least 3 edges and each edge borders at most 2 faces: $3F \le 2E$ . Substituting into Euler gives the bound.

For a bipartite planar simple graph (no odd cycles, so face length $\ge 4$ ): $E \le 2V - 4$

Non-planar examples

$K_5$ : $V=5$ , $E=10$ . Bound says $E \le 3(5)-6 = 9$ . So $K_5$ is non-planar.
$K_{3,3}$ : bipartite, $V=6$ , $E=9$ . Bound: $E \le 2(6)-4 = 8$ . Hence non-planar.

Kuratowski's theorem

A graph is planar iff it does not contain a subdivision of $K_5$ or $K_{3,3}$ .

Wagner's theorem (equivalent)

A graph is planar iff it has neither $K_5$ nor $K_{3,3}$ as a minor.

Why this matters in Data Science

VLSI layout, network topology, map drawing, graph visualization.

Mind Map

Visual structure of the concept

PLANAR GRAPHS
├── Definition: drawable without crossings
├── Plane embedding ⇒ Faces
├── Euler formula: V − E + F = 2
├── Edge bounds
│   ├── Simple planar: E ≤ 3V − 6
│   └── Bipartite planar: E ≤ 2V − 4
├── Non-planar
│   ├── K₅       (5 vertices, 10 edges)
│   └── K₃,₃    (bipartite, 9 edges)
└── Characterizations
    ├── Kuratowski: no K₅ / K₃,₃ subdivision
    └── Wagner:     no K₅ / K₃,₃ minor

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define a planar graph. A graph that can be drawn in the plane such that no two edges cross.

Q2. State Euler's formula for connected planar graphs. $V - E + F = 2$ .

Q3. Why is $K_5$ non-planar? $E = 10 > 3V - 6 = 9$ , violating the planarity edge bound.

Q4. State Kuratowski's theorem. A graph is planar iff it contains no subdivision of $K_5$ or $K_{3,3}$ .

Part B (20 marks)

Q. State and prove Euler's formula for planar graphs. Derive the edge bound $E \le 3V - 6$ and use it to prove that $K_5$ and $K_{3,3}$ are non-planar.

Euler's formula. For any connected planar graph, $V - E + F = 2$ .

Proof by induction on $E$ . Base $E = V - 1$ : The graph is a tree, $F = 1$ (only the outer face). Then $V - E + F = V - (V-1) + 1 = 2$ . ✓

Inductive step. Assume the formula for any connected planar graph with $E - 1$ edges. Take a connected planar graph with $E$ edges. If it has a cycle, remove one edge from the cycle. The graph remains connected, the number of faces decreases by 1 (two faces merge into one). The relation $V - (E-1) + (F-1) = 2$ gives $V - E + F = 2$ . ∎

Edge bound for a simple connected planar graph with $V \ge 3$ .

Each face is bounded by at least 3 edges, and each edge borders at most 2 faces: $3F \le 2E \Rightarrow F \le \frac{2E}{3}$ Substitute into Euler: $V - E + \frac{2E}{3} \ge 2 \Rightarrow V - \frac{E}{3} \ge 2 \Rightarrow E \le 3V - 6.$

$K_5$ is non-planar. $V = 5$ , $E = 10$ . Bound: $E \le 3(5) - 6 = 9$ . But $10 > 9$ — contradiction. So $K_5$ is non-planar.

$K_{3,3}$ is non-planar. It is bipartite, so every cycle has length $\ge 4$ and every face $\ge 4$ edges. Hence $4F \le 2E$ , giving $E \le 2V - 4$ . For $K_{3,3}$ : $V = 6$ , $E = 9$ . Bound: $E \le 2(6) - 4 = 8$ . But $9 > 8$ — contradiction. So $K_{3,3}$ is non-planar. ∎

Planar Graphs