Planar graph

Key Defination:

• A planar embedding of $G$ is a drawing of $G$ on the plane such that vertices are different points and edges are lines that join vertices s.t. they do not intersect (except at common endpoints)
• A graph that has a planar embedding is a planar graph.
• A face of a planar embedding is a connected region on the plane (not separated by lines). Two faces are adjacent if they share at least two edges.
• For a connected planar graph, the boundary walk of a face is a closed walk on the edges around the boundry of the region once around. The degree of the face is the length of its boundry walk.
• Handshaking lemma for Faces:
  • Let $G$ be a planar graph with a planar embedding when $F$ is the set of all faces. Then $$ \sum_{f\in F} deg(f) = 2 |E(G)|$$
  • proof: each edge contributes 2 to the sum of face degrees. One for each side of the edge.

Observation: if $e$ is a bridge, then the two sides of $e$ are in the same face. Otherwise, they are in different faces, since $e$ is in a cycle.

Jordan Curve theorem:

• Every single closed curve (cycle) on the plane separates the plane into 2 parts, one inside and one outside

Euler's Formula

• A graph can be different embedding, consider n represents the number of vertices, m represents the number of edges, s represents the number of faces: then we have, \[ \begin{aligned} n - m + s &= 2 \\ n - m + s &= 1 + (\text{#}\,\,\text{of} \,\, \text{components}) \end{aligned} \]
• Theorem: For a connected planar graph with an embedding with n vertices, m edges and s faces: $n - m + s = 2$

Proof by induction: (fix n) inducted on m

Base case: $m = n - 1$ (spanning tree), thus $s=1$ (no cycles, only one face) \rightarrow the statement holds

Inductive Hypotheses: Assume Euler's formula holds for any connected planar graph with n vertices, $m-1$ edges

Inductive Step: Suppose $G$ is connected, planar, n vertices, m edges and s faces

Let $e$ be an edge in a cycle of $G$, then $G - e$ is connected an planar.

The two sides of $e$ and different faces in $G$, and they merge into one faces in $G-e$ \rightarrow $s-1$ faces

By Inductive Hypotheses, the Euler's formula holds for $G-e$

So $n-(m-1) + (s-1) = 2 \Rightarrow n - m + 1 + s -1 = n - m + s = 2$

Platonic Solids

If $G$ can be embedded on a planar, then $G$ can be embedded on a sphere. We then cut across each face to obtain a polyhedron.

Definition: a connected planar graph is platonic if it has an embedding where every vertex has same degree $(\ge 3)$ and every face has some degree.

• When $d_v=3, d_f=3, n=4, m=6, s=4$, it is a tetrahedron
• When $d_v=3, d_f=4, n=8, m=12, s=6$ it is a cube
• When $d_v=4, d_f=3, n=6, m=12, s=8$, it is a octahedron
• when $d_v=3, d_f=5, n=20, m=30, s=12$, it is a dodecahedron
• When $d_v=5, d_f=3, n=12, m=30, s=20$, it is a icosahedron

Non-planar graphs

Key definitions

• One way to prove non-planar graph is to show that it has more than 3n-6 edges
• When $n\ge 3$, a connected planar graph on n vertices has at most3n - 6 edges
• Proof:
  Consider a planar embedding of G with $n \ge 3$ vertices, m edges and s faces.
  If G is a tree, then we have $m = n-1$ edges, where $n-1 \le 3n-6$ is satisfied for $n\ge 3$
  If G is a tree, then G has a cycle, there are at least 2 faces, each face boundary must contains a cycle to separate from other faces (Jordan curve theorem). So each face has degree at least 3.
  By handshaking lemma for faces, $2m = \sum_{f\in F}^{deg(f)} \ge 3 \cdot s$
  So $2m \ge 3m = 3 (2 - n +m) by Euler's formula
  Therefore $m \le 3n-6$
• Note Disconnected planar graphs have "fewer" edges that a connected one, so that applies to disconnected graph as well.
• Corollary: $k_5$ is not planar, same with $k_{3,3}$
• Theorem: A connected bipartite planar graph has at least 3 vertices has at most 2n-4 edges
• Kuratowski's Theorem:
  • An edge subdivision of G is obtained by replacing each edge of G with a new path of length at least 1 (i.e. introducing new vertices of degree 2 to the edges) Observation: G is a planar iff every edge subdivision is a planar.
  • G is planar iff G does not contain an edge subdivision of $k_5$ and $k_{3,3}$
  • Note: do not repeat vertices or edges in the subdivision