Euler’s Formula (Planar Graphs)

Context: FIT1058_MOC · $n-m+f=2$ for a connected plane graph · yields the edge bounds proving $K_5$, $K_{3,3}$ nonplanar

Quick Revision

• 🎯 Objective: $n-m+f=2$ for a connected plane graph ➔ invariant across drawings.
• 📦 Core Components: derive $m\le 3n-6$ (and $2n-4$ triangle-free) ➔ prove $K_5,K_{3,3}$ nonplanar.
• ⚡ Key Constraint: bounds are necessary, not sufficient; passing $3n-6$ doesn’t prove planarity.

📝 Core

1. The Formula

• Statement ➔ connected plane graph: $n-m+f=2$ ($f$ counts the outer face).
• Invariant ➔ same for all crossing-free drawings (proved by induction).

2. The Edge Bounds

• General ➔ faces have $\ge 3$ sides ⟹ $3f\le 2m$ ⟹ $m\le 3n-6$ ($n\ge 3$).
• Triangle-free ➔ faces $\ge 4$ sides ⟹ $m\le 2n-4$.

3. The Obstructions

• $K_5$ ➔ $m=10>9=3n-6$ ⟹ nonplanar.
• $K_{3,3}$ ➔ passes $3n-6$ but bipartite ⟹ triangle-free ⟹ $9>8=2n-4$.

Key identities:

$\text{each face}\ge 3\text{ sides},\text{each edge}=2\text{ sides}\Rightarrow 3f\le 2m\Rightarrow f\le \frac{2m}{3}$ $f=2-n+m\Rightarrow 2-n+m\le \frac{2m}{3}\Rightarrow m\le 3n-6$

When It Flips: the "sides $=2m$" double-count parallels the degree-sum argument. Faces depend on connectivity; $n-m+f=2$ assumes the plane graph is connected.

📊 Exam Execution Trace

Applied Exercise

Problem: A connected plane graph has $n=8$, $m=10$. Find $f$; test $K_5$. Derivation Proof / Hand-Calculation Walkthrough:

$$\begin{array}{rl}f& =2-n+m=2-8+10=4\\ K_5& :m=10>3(5)-6=9\Rightarrow \text{nonplanar}\end{array}$$

Final Extracted Output: $f=4$ (satisfies $8-10+4=2$); $K_5$ nonplanar.

⚠️ Common Mistakes

• 💡 Necessary, not sufficient ➔ $K_{3,3}$ passes $m\le 3n-6$ yet is nonplanar; only a violation proves nonplanarity.

🧠 Active Recall

State Euler's formula and derive $m\le 3n-6$.

• Hint: Double-count sides.

Answer

• Short answer: $n-m+f=2$; faces $\ge 3$ sides, edges 2 sides ⟹ $3f\le 2m$; substitute $f=2-n+m$.
• Why: Rearrange ➔ $2-n+m\le \frac{2m}{3}$ gives $m\le 3n-6$.

Prove $K_5$ and $K_{3,3}$ are nonplanar.

• Hint: Two bounds.

Answer

• Short answer: $K_5$: $10>9=3n-6$; $K_{3,3}$: triangle-free, $9>8=2n-4$.
• Why: Minimal obstructions ➔ the two smallest nonplanar graphs.