10.3 Planar Graphs, Euler's Polyhedral Formula & Kuratowski's Non-Planar Minors

Back to Discrete Mathematics Notes

📚Module 10: Advanced Graph Theory: Trees, Planarity & ColoringTopic 10.3: Planar Graphs & Euler's Formula⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Printed Circuit Boards & The Three Utilities Puzzle

Think of laying electrical wires on a flat surface without short-circuits:

1. The Planar Standard (Zero Short-Circuits): When designing a single-layer Printed Circuit Board (PCB), copper conductive traces cannot cross each other. If two traces cross, they cause an electrical short-circuit. A graph is Planar if you can draw all its vertices and edges on a flat 2D plane with zero crossing edges!
2. The Three Utilities Puzzle ($K_{3, 3}$): Three houses need connections to three public utilities (Water, Gas, Electricity). Can you connect all 3 houses to all 3 utilities without any two underground pipes crossing? In 1930, Kazimierz Kuratowski proved it is physically impossible: $K_{3, 3}$ is a fundamental obstruction to planarity!
3. Euler's Polyhedral Law ($V - E + R = 2$): Whenever you draw a non-crossing graph on a plane, it cuts the surface into distinct enclosed geographical regions (faces). The relationship between vertices ($V$), edges ($E$), and regions ($R$) is an unbreakable geometric law of our 3D physical universe!

💻 Bridging to Computer Science: VLSI Chip Routing, Map Projection & Dual Meshes

In computer systems:

• VLSI Layout & Chip Routing: Microchip designers minimize expensive silicon metal layers by ensuring local subcircuits are planar, routing signals on single layers without via hole layer-crossings.
• Computational Geometry & GIS: Geographic Information Systems (Google Maps) represent road networks and terrain meshes as planar straight-line graphs (PSLG) to accelerate polygon spatial queries.
• Mesh Generation & 3D Computer Graphics: Dual planar graphs ($G^*$) convert triangular surface meshes into Voronoi diagrams and Delaunay triangulations for realistic 3D lighting shaders.

📑Table of Contents

• 🗺️ Planar Graphs, Embeddings & Face Degrees
• 🏛️ Euler's Polyhedral Formula (1752)
• ⚖️ Planar Edge Density Bounds
• 🚫 The Canonical Non-Planar Obstructions: K₅ and K₃,₃
• 🔍 Kuratowski's & Wagner's Characterization Theorems
• 📝 Step-by-Step Worked Examples
  • Example 1: Applying Euler's Formula to a Polyhedral Graph
  • Example 2: Proving Non-Planarity of the Petersen Graph
• 🎯 Exam & Interview Pitfall Check

---

🗺️ Planar Graphs, Embeddings & Face Degrees

📖Definition 10.5: Planar Graph and Plane Graphdefinition

1. Planar Graph: A graph $G$ is called planar if it can be drawn in the Euclidean plane $\mathbb{R}^2$ (or on the surface of a sphere) such that no two edges intersect or cross each other except at their common endpoints.
2. Plane Graph: A specific non-crossing 2D drawing of a planar graph. (Planarity is an abstract property of the graph; a plane graph is its concrete physical embedding).
3. Regions (Faces): A plane graph divides the 2D plane into contiguous regions (faces). Exactly one region is unbounded (the exterior region), while the remaining regions are bounded interior polygons.

⚡Law 10.1: Handshaking Lemma for Faceslaw

Let $R$ be the set of regions in a plane graph $G$.

1. The degree of a face (denoted $\deg(f)$) is the number of edges along its boundary perimeter.
   • If an edge acts as a bridge sticking into a face, that edge is traversed twice in the boundary perimeter, contributing +2 to the face degree!
2. Handshaking Lemma for Faces: $$\sum_{f \in R} \deg(f) = 2 |E|$$ (Every edge bounds either two distinct regions, or bounds the same region on both sides, contributing exactly 2 to the sum of face degrees).

---

🏛️ Euler's Polyhedral Formula (1752)

📐Theorem 10.7: Euler's Formula for Planar Graphstheorem

For any connected planar graph drawn with $V$ vertices, $E$ edges, and $R$ regions:

$$V - E + R = 2$$

Proof by Induction on the Number of Edges $E$:

• Base Case (A Tree): A connected acyclic graph on $V$ vertices has $E = V - 1$ edges and exactly 1 region (the exterior face, $R = 1$): $$V - E + R = V - (V - 1) + 1 = 1 + 1 = 2 \quad (\text{Holds!})$$
• Inductive Step: Suppose Euler's formula holds for all connected plane graphs with $E - 1$ edges. Let $G$ have $E$ edges and at least one cycle (if $G$ has no cycles, it is a tree and base case applies).
  • Pick an edge $e$ that belongs to a cycle.
  • Edge $e$ separates two distinct regions. Deleting edge $e$ merges those two regions into one, reducing the region count by 1 ($R' = R - 1$) and edge count by 1 ($E' = E - 1$), while leaving $V$ unchanged ($V' = V$).
  • The resulting graph $G - e$ is still connected with $E - 1$ edges. By induction hypothesis: $$V' - E' + R' = 2 \implies V - (E - 1) + (R - 1) = 2 \implies V - E + R = 2$$

Therefore, Euler's formula holds for all connected plane graphs!

Disconnected Extension: If a planar graph has $k \ge 1$ connected components:

$$V - E + R = 1 + k$$

---

⚖️ Planar Edge Density Bounds

Euler's formula places strict mathematical limits on how many edges a planar graph can accommodate.

📐Theorem 10.8: General Planar Edge Density Boundtheorem

In any simple connected planar graph with $V \ge 3$ vertices:

$$|E| \le 3 |V| - 6$$

Proof:

1. In a simple graph with $V \ge 3$, every face must be bounded by at least 3 edges: $$\forall f \in R, \quad \deg(f) \ge 3$$
2. Summing over all $R$ faces using the Face Handshaking Lemma: $$2 |E| = \sum_{f \in R} \deg(f) \ge 3 R \implies R \le \frac{2}{3} |E|$$
3. Substitute $R \le \frac{2}{3} |E|$ into Euler's formula ($V - E + R = 2$): $$2 = V - E + R \le V - E + \frac{2}{3} E = V - \frac{1}{3} E$$
4. Rearranging: $$\frac{1}{3} |E| \le |V| - 2 \implies |E| \le 3 |V| - 6$$

📐Theorem 10.9: Triangle-Free Planar Edge Density Boundtheorem

In any simple connected planar graph with $V \ge 3$ vertices that has NO triangles (e.g., all Bipartite Graphs, or graphs with girth $\ge 4$):

$$|E| \le 2 |V| - 4$$

Proof: Because the graph has no triangles, every face must be bounded by at least 4 edges: $\deg(f) \ge 4$.

$$2 |E| = \sum \deg(f) \ge 4 R \implies R \le \frac{1}{2} |E|$$

Substitute into Euler's formula:

$$2 = V - E + R \le V - E + \frac{1}{2} E = V - \frac{1}{2} E \implies |E| \le 2 |V| - 4$$

---

🚫 The Canonical Non-Planar Obstructions: K₅ and K₃,₃

The Two Incurable Non-Planar Obstructions: K₅ vs K₃,₃

The fundamental geometric bottlenecks that prevent 2D embedding

K₅ Obstruction

Complete Graph K₅

⭐

Dominant Architecture / DomainClique Obstruction

• •Parameters: |V| = 5 vertices, |E| = C(5, 2) = 10 edges.
• •Planar Limit: |E| ≤ 3|V| - 6 = 3(5) - 6 = 9 edges.
• •Violation: |E| = 10 > 9! Exceeds maximum edge capacity.
• •Conclusion: K₅ is strictly NON-PLANAR!

"Too many edges for 5 vertices in 2D space."

K₃,₃ Obstruction

Complete Bipartite Graph K₃,₃

🏠

Dominant Architecture / DomainUtilities Puzzle Obstruction

• •Parameters: |V| = 6 vertices, |E| = 3 × 3 = 9 edges.
• •Property: Bipartite ⟹ Triangle-free (girth ≥ 4).
• •Planar Limit: |E| ≤ 2|V| - 4 = 2(6) - 4 = 8 edges.
• •Violation: |E| = 9 > 8! Exceeds triangle-free planar capacity.
• •Conclusion: K₃,₃ is strictly NON-PLANAR!

"Bipartite structure forces wider faces that exceed planar area."

✓ Kuratowski’s Theorem: Non-Planar Minors

Kuratowski Invariant: A finite graph is planar if and only if it does not contain a subgraph homeomorphic to or contractible to K₅ or K₃,₃.

---

🔍 Kuratowski's & Wagner's Characterization Theorems

How do we prove whether an arbitrary complex graph is planar?

📐Theorem 10.10: Kuratowski's Theorem (1930)theorem

A graph $G$ is planar if and only if it contains NO subgraph that is homeomorphic to $K_5$ or $K_{3, 3}$!

• Subdivision (Homeomorphism): An elementary subdivision replaces an edge $\{u, v\}$ with two edges $\{u, w\}$ and $\{w, v\}$ by inserting a new vertex $w$ of degree 2. Two graphs are homeomorphic if both can be obtained from the same graph by a sequence of elementary subdivisions.
• Intuition: If you can find $K_5$ or $K_{3, 3}$ hidden inside a graph (even if its edges are subdivided into multi-hop paths), the graph is guaranteed to be non-planar!

📐Theorem 10.11: Wagner's Theorem (1937)theorem

A graph $G$ is planar if and only if neither $K_5$ nor $K_{3, 3}$ is a minor of $G$!

• Graph Minor: A graph $H$ is a minor of $G$ if $H$ can be formed from $G$ by deleting vertices, deleting edges, and contracting edges (merging adjacent endpoints into a single vertex).

---

📝 Step-by-Step Worked Examples

Example 1: Applying Euler's Formula to a Polyhedral Graph

Problem Statement: A connected planar graph has 12 vertices, and every vertex has degree 3 (a 3-regular graph, like a truncated tetrahedron).

1. How many edges does the graph contain?
2. How many regions (faces) does this graph divide the plane into?
3. If every face is either a triangle ($\deg = 3$) or a hexagon ($\deg = 6$), and there are 4 triangles, how many hexagons are there?

Step-by-Step Solution:

1. Step 1: Calculate Total Edges via Handshaking Lemma

   • Vertices $V = 12$, and every vertex has degree 3.
   • $\sum \deg(v) = 12 \times 3 = 36$.
   • By Handshaking: $2 |E| = 36 \implies |E| = 18$ edges.

2. Step 2: Calculate Regions via Euler's Formula

   • $V - E + R = 2$
   • $12 - 18 + R = 2 \implies -6 + R = 2 \implies R = 8$ regions.

3. Step 3: Determine Face Distribution

   • Total regions $R = 8$.
   • Let $T$ be the number of triangles, and $H$ be the number of hexagons.
   • $T + H = 8$. Given $T = 4 \implies H = 8 - 4 = 4$ hexagons.
   • Verification via Face Handshaking: $$\sum \deg(f) = 4(3) + 4(6) = 12 + 24 = 36 = 2 |E| = 2(18) = 36 \quad (\text{Perfect!})$$

Key Takeaway: Euler's formula seamlessly links physical polyhedron faces to planar graph vertex degrees.

---

Example 2: Proving Non-Planarity of the Petersen Graph

Problem Statement: The Petersen Graph has $n = 10$ vertices and $m = 15$ edges. Its shortest cycle has length 5 (girth = 5). Prove that the Petersen Graph is non-planar:

1. Using face degree inequality bounds.
2. Using Kuratowski's minor theorem.

Step-by-Step Solution:

1. Method 1: Edge Bound Verification

   • The Petersen graph has girth $g = 5$ (no cycles of length 3 or 4).
   • Therefore, in any hypothetical plane drawing, every face must have $\deg(f) \ge 5$.
   • By the Face Handshaking Lemma: $$2 |E| = \sum \deg(f) \ge 5 R \implies R \le \frac{2}{5} |E| = \frac{2}{5}(15) = 6$$
   • Substitute into Euler's formula: $$V - E + R = 10 - 15 + R = -5 + R$$ $$-5 + R \le -5 + 6 = 1 < 2!$$
   • Euler's formula requires $V - E + R = 2$, but the maximum possible value is only $1$!
   • This contradiction proves that the Petersen Graph cannot be planar!

2. Method 2: Kuratowski Minor Verification

   • Contracting the 5 cross-spoke edges of the Petersen graph merges the inner 5-star cycle into the outer 5-ring cycle, directly producing the complete graph $K_5$ as a minor!
   • By Wagner's Theorem, because $K_5$ is a minor, the Petersen Graph is strictly non-planar!

Key Takeaway: When standard $3V - 6$ bounds do not immediately fail, checking girth inequalities ($2E \ge g \cdot R$) rigorously proves non-planarity.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If a graph satisfies $|E| \le 3|V| - 6$, is it guaranteed to be planar? Key Focus Points: No! The condition $|E| \le 3|V| - 6$ is a necessary condition for planarity, NOT a sufficient condition! For example, $K_{3, 3}$ has $V = 6$ and $E = 9$. Evaluating the bound:

$$3(6) - 6 = 18 - 6 = 12 \ge 9$$

$K_{3, 3}$ passes the $3V - 6$ test, yet $K_{3, 3}$ is completely non-planar! (It fails the tighter triangle-free bound $2V - 4 = 8 < 9$).

Question 2: Can a planar graph have a minimum vertex degree $\delta(G) \ge 6$? Key Focus Points: Never! In any simple planar graph:

$$\sum \deg(v) = 2 |E| \le 2(3V - 6) = 6V - 12$$

The average degree is $\frac{2|E|}{V} \le \frac{6V - 12}{V} = 6 - \frac{12}{V} < 6$. Because the average degree is strictly less than 6, every planar graph must contain at least one vertex of degree $\le 5$!

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting the exterior (unbounded) face in Euler's formula Why it fails: In $V - E + R = 2$, students often count only the interior polygons, forgetting that the surrounding infinite exterior space is also a valid region! Omitting the exterior face gives $V - E + R = 1$, which is invalid.

Trap 2: Applying $2V - 4$ to graphs with triangles Why it fails: The tighter bound $|E| \le 2|V| - 4$ requires the graph to have girth $\ge 4$ (no triangles). If a graph contains even a single triangle, faces of degree 3 are permitted, and you must use the general bound $|E| \le 3|V| - 6$.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic10.2 Trees, Properties of Spanning Trees & Cayley's FormulaNext Topic →10.4 Graph Coloring, Chromatic Number Bounds & the Four Color Theorem