Unit 7: Planar Graphs, Euler's Formula, Kuratowski's Theorem & Duality

1. Planar Graphs and Planar Embeddings

A graph is an abstract topological entity. When drawn in a continuous geometric space, edges may or may not cross.

Definition 7.1 (Planar Graph and Plane Graph):

1. A graph $G$ is called planar if it can be drawn in the Euclidean plane $\mathbb{R}^2$ (or on the 2-sphere $S^2$) such that no two edges intersect, except at their common endpoints.
2. A specific non-crossing drawing of a planar graph in $\mathbb{R}^2$ is called a planar embedding (or a plane graph).

2. Faces and Regions of a Plane Graph

A planar embedding partitions the plane $\mathbb{R}^2 \setminus G$ into topologically connected open domains called faces (or regions).

Definition 7.2 (Faces and the Outer Face): Let $G$ be a plane graph.

• The connected components of $\mathbb{R}^2 \setminus G$ are the faces of $G$.
• Exactly one face is unbounded, called the exterior face (or infinite face).
• All other faces are bounded, called interior faces.
• The boundary of a face $f$ consists of the vertices and edges that enclose $f$.
• The degree of a face $f$, denoted $\deg(f)$, is the number of edges along its boundary (with cut-edges counted twice).

Theorem 7.1 (Handshaking Lemma for Faces): In any plane graph $G$ with edge set $E$ and face set $F$:

Proof:

Every edge either separates two distinct faces $f_1 \ne f_2$ (contributing 1 to $\deg(f_1)$ and 1 to $\deg(f_2)$), or is a bridge surrounded on both sides by the same face $f$ (contributing 2 to $\deg(f)$). In either case, each edge contributes exactly 2 to the sum of face degrees. $\blacksquare$

1. Euler's Formula for Connected Plane Graphs

Published by Leonhard Euler in 1758 for convex 3D polyhedra, this formula forms the bedrock of topological graph theory:

Theorem 7.2 (Euler's Formula): Let $G$ be a connected plane graph with $V$ vertices, $E$ edges, and $F$ faces. Then:

Complete Formal Proof (by Induction on Edges):

We prove the formula by induction on the number of edges $E$ for any connected plane graph on $V$ vertices:

• Base Case (Trees):

If $G$ contains no cycles, then $G$ is a tree. By Theorem 3.1, $E = V - 1$. Since a tree contains no cycles, it does not divide the plane into interior faces; it has only the single unbounded exterior face: $F = 1$. Substituting these values:

The base case holds with exact equality!

• Inductive Step:

Assume the formula $V - E + F = 2$ holds for all connected plane graphs with strictly fewer than $E$ edges. Let $G$ be a connected plane graph with $E$ edges that is not a tree. Since $G$ is not a tree, $G$ must contain at least one simple cycle $C$. Choose an edge $e$ lying on the cycle $C$. By the Jordan Curve Theorem, the cycle $C$ separates the plane into an interior domain and an exterior domain. Therefore, the edge $e$ lies on the boundary of two distinct faces $f_1 \ne f_2$. Now, remove the edge $e$ from $G$, forming the graph $G' = G - e$. Notice:

1. Since $e$ lay on a cycle, $G'$ remains connected.
2. The vertex count is unchanged: $V' = V$.
3. The edge count decreases by 1: $E' = E - 1$.
4. The two faces $f_1$ and $f_2$ merge into a single unified face in $G'$, so the face count decreases by 1: $F' = F - 1$.

By the induction hypothesis applied to $G'$:

Substituting $V' = V$, $E' = E - 1$, and $F' = F - 1$:

Therefore, $V - E + F = 2$ holds for all connected plane graphs. $\blacksquare$

Corollary 7.2.1 (Disconnected Planar Graphs): If a planar graph $G$ has $\omega(G) = k$ connected components:

1. Maximum Edges in Simple Planar Graphs

In a simple plane graph, every face boundary must contain at least 3 edges (no self-loops or multiple edges):

Theorem 7.3 (Planar Edge Upper Bound): In any simple planar graph $G$ with $V \ge 3$ vertices and $E$ edges:

If $G$ is triangle-free (contains no $C_3$, such as a bipartite graph):

Complete Proof:

1. General Bound ($E \le 3V - 6$):

By the Face Handshaking Lemma (Theorem 7.1) and $\deg(f) \ge 3$:

Substitute this into Euler's formula $V - E + F = 2$:

2. Triangle-Free Bound ($E \le 2V - 4$):

If $G$ contains no triangles, then every face boundary must have at least 4 edges: $\deg(f) \ge 4$.

Substitute into Euler's formula:

2. The Canonical Non-Planar Graphs: $K_5$ and $K_{3,3}$

Theorem 7.4 (Non-Planarity of $K_5$ and $K_{3,3}$):

1. The complete graph $K_5$ is non-planar.
2. The complete bipartite graph $K_{3,3}$ (the Utility Graph) is non-planar.

Proof of 1 ($K_5$):

For $K_5$, vertex count $V = 5$, edge count $E = \binom{5}{2} = 10$. If $K_5$ were planar, it would satisfy Theorem 7.3:

$10 \le 9$ is a contradiction! Therefore, $K_5$ is non-planar. $\blacksquare$

Proof of 2 ($K_{3,3}$):

For $K_{3,3}$, vertex count $V = 3 + 3 = 6$, edge count $E = 3 \times 3 = 9$. $K_{3,3}$ is bipartite, so it contains no odd cycles; in particular, it is triangle-free! If $K_{3,3}$ were planar, it would satisfy the triangle-free bound:

$9 \le 8$ is a contradiction! Therefore, $K_{3,3}$ is non-planar. $\blacksquare$

1. Graph Subdivisions and Homeomorphism

Definition 7.3 (Elementary Subdivision): An elementary subdivision of an edge $e = \{u, v\}$ is the operation of replacing $e$ with two edges $\{u, w\}$ and $\{w, v\}$ by inserting a new vertex $w$ of degree 2. Two graphs $G_1$ and $G_2$ are homeomorphic (or topological minors) if both can be obtained from the same graph by a sequence of elementary subdivisions.

A graph $H$ is a subdivision of $K$ if $H$ can be obtained from $K$ by subdividing zero or more edges. Notice that subdividing an edge does not change planarity: $G$ is planar if and only if any subdivision of $G$ is planar.

2. Kuratowski's Theorem

In 1930, Polish mathematician Kazimierz Kuratowski established the definitive characterization of planarity:

Theorem 7.5 (Kuratowski's Theorem, 1930): A graph $G$ is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or $K_{3,3}$.

3. Wagner's Theorem and Graph Minors

In 1937, Klaus Wagner formulated an alternative characterization based on minor operations:

• Minor Operations: Edge deletion, vertex deletion, and edge contraction (merging the two endpoints of an edge).
• A graph $H$ is a minor of $G$ if $H$ can be obtained from $G$ by a finite sequence of deletions and contractions.

Theorem 7.6 (Wagner's Theorem, 1937): A graph $G$ is planar if and only if it contains neither $K_5$ nor $K_{3,3}$ as a minor.

1. Construction of the Geometric Dual $G^*$

Let $G$ be a plane graph with vertex set $V$, edge set $E$, and face set $F$.

Definition 7.4 (Geometric Dual $G^$): The geometric dual $G^ = (V^, E^)$ is constructed as follows:

1. For each face $f_i \in F(G)$, place a corresponding dual vertex $v_i^ \in V^$.
2. For each edge $e \in E(G)$ that separates face $f_i$ and face $f_j$, draw a dual edge $e^ \in E^$ connecting $v_i^$ and $v_j^$, crossing $e$ exactly once.

(If $e$ is surrounded on both sides by the same face $f_i$, $e^$ is a self-loop on $v_i^$).

Dual Parameters:

If $G$ is connected, then $(G^)^ \cong G$ (the dual of the dual is isomorphic to the primal graph).

2. Whitney's Planar Duality Theorem

Theorem 7.7 (Whitney's Duality Theorem, 1932): A graph $G$ is planar if and only if it possesses a combinatorial dual: That is, there exists a graph $G^$ and an edge bijection $\phi: E(G) \to E(G^)$ such that for every subset $S \subseteq E(G)$: