> [!NOTE] Theorem (Euler's Formula (Euler/Cauchy/etc, 1750-1811)). > For a drawing of a connected [[Crossing number (graph theory)|planar graph]], $|V|-|E|+|F|=2$. # Proofs ###### Proof by induction We use induction on the number of vertices. Clearly the 1-vertex tree is planar. We know that a tree $G$ contains a leaf - remove it, and by assumption we get a planar graph; draw that graph, then draw the leaf back in without hitting the rest of the graph to get a drawing of $G$. Let $G$ be a connected planar graph. Pick a planar drawing of $G$, with vertex/edge/face sets $V, E, F$. Let $T$ be a spanning tree of $G$ - we automatically have a planar drawing of $T$, just by deleting all edges of $G$ not in $T$ from our drawing. The drawing of $T$ has 1 face, since the boundary of any (non-outer) face contains a cycle, and $T$ has no cycles. Now we add back in the edges of $G$ not in $T$, one by one. Since $T$ has $|V|-1$ edges, there are $|E|-(|V|-1)$ edges to add back in. Let $G_0=T$, and we get a sequence of graphs $ G_1, \ldots, G_{|E|-(|V|-2)}, G_{|E|-(|V|-1)}=G . $ Call the $i$ th edge we add this way $e_i$. When we add $e_i$ to $G_{i-1}$, it divides a face of $G_{i-1}$ into two faces in $G_i$. (As you walk down $e_i$ in $G_i$, there is a face on your left and a face on your right. These can't be part of the same face, since if they were, then that face would separate the two endpoints of $e_i$ into two different components of the graph, whereas we know $G_{i-1}$ is connected.) Thus $G_i$ has one more face than $G_{i-1}$. Since $T$ has 1 face, we conclude that $G$ has $1+|E|-(|V|-1)$ faces. That is, $F=2+|E|-|V|$, or $|V|-|E|+|F|=2$. ###### Proof using dual-graphs # Applications - [[Pick's Theorem]]. - classification of convex polyhedra (platonic solids)