Euler's Formula for Connected Plane Graphs

From a Spanning Tree to a Face Count

A plane graph is a graph together with a fixed drawing in the plane in which edges meet only at common endpoints. Its faces are the connected regions of the plane left after removing the drawing; the unbounded region counts as a face. Write \(V=V(G)\) for the vertex set, \(E=E(G)\) for the edge set, \(n=|V|\) for the order, \(m=|E|\) for the size, and \(F\) for the number of faces. Throughout, graphs are finite and simple, and a connected graph is assumed to have at least one vertex.

The central idea is to begin with a spanning tree of the graph. A spanning tree uses all the vertices but has no cycles. When the other edges are restored in their original positions, each one splits a face in two. Thus the face count can be found by counting how many edges were restored.

Two facts about the starting tree and the edge-restoration process are useful. A finite connected graph has a spanning tree with \(n-1\) edges. Also, the earlier result on trees in plane embeddings says that a plane tree has exactly one face. Finally, the earlier result on how edge insertion changes face counts says that, when an edge is added inside a face between vertices already connected in the current plane graph, that face is split into two. The number of faces therefore increases by exactly one. We will apply this last fact only to edges in the original plane embedding, so the inserted edge has no crossings with the current drawing.

Why a Spanning Tree Has \(n-1\) Edges

We first justify the edge count that will determine how many edges must be restored.

Proof. Since \(G\) is finite, among its connected spanning subgraphs choose one, \(T\), with as few edges as possible. If \(T\) contained a cycle, removing one edge of that cycle would leave its endpoints connected by the rest of the cycle. Every route in \(T\) that used the removed edge could use that alternative route instead, so the resulting spanning subgraph would still be connected. This contradicts the minimal choice of \(T\). Thus \(T\) is connected and acyclic, hence a spanning tree.

We prove the edge count for trees by induction on the number \(n\) of vertices. For \(n=1\), a tree has no edges, so it has \(0=1-1\) edges. Now let \(n\geq 2\), and suppose the claim holds for trees on \(n-1\) vertices. A longest path in a finite tree has an endpoint of degree one: if an endpoint had another neighbor, that neighbor could not already be on the path, since that would create a cycle, and so the path could be extended. Remove this endpoint and its one incident edge. The remaining graph is connected, because a degree-one vertex cannot be an internal vertex of a path between two remaining vertices; it is also acyclic. It is therefore a tree on \(n-1\) vertices, with \(n-2\) edges by induction. Putting back the removed edge gives \(n-1\) edges. \(\square\)

In particular, if \(T\) is a spanning tree of an \(n\)-vertex graph with \(m\) edges, then the number of edges of \(G\) outside \(T\) is \(m-(n-1)\). The tree result above gives the base face count, and edge insertion gives one additional face for each of those remaining edges.

Euler’s Formula for Connected Plane Graphs

Proof. Choose a spanning tree \(T\) of \(G\). It has all \(n\) vertices and exactly \(n-1\) edges. Keeping the original embedding and deleting the edges outside \(T\) gives a plane embedding of \(T\). Since a plane tree has one face, this starting drawing has \(F_T=1\).

Restore the \(m-(n-1)\) deleted edges one at a time, using their original positions in the plane embedding of \(G\). Before each restoration, the current graph contains \(T\), so it is connected. The endpoints of the edge being restored are therefore already connected. Its arc does not cross the current drawing, because all edges come from the fixed embedding of \(G\). By the edge-insertion result, each restored edge increases the face count by exactly one. After all \(m-(n-1)\) edges have been restored, the face count is

Rearranging gives \(n-m+F=2\), which is the claimed formula. This also covers the single-vertex graph: it has \(n=1\), \(m=0\), and \(F=1\), so \(1-0+1=2\). \(\square\)

The proof explains why connectedness matters to this argument: the spanning tree supplies a connected starting drawing, and every edge is restored between vertices that are already connected. The theorem concerns a plane graph, where faces belong to a specified embedding. The result is that for any such connected embedding, the vertex, edge and face counts satisfy the same equation.

Worked Examples

Common Pitfalls and Uses

Confusing a plane graph with a planar graph. A planar graph is an abstract graph that can be drawn without crossings; a plane graph comes with one such drawing. In this tutorial, \(F\) counts regions in the specified drawing. The theorem applies to a connected plane graph, not to a crossing drawing in which faces have not been defined by a plane embedding.

Forgetting to count the unbounded face. In the pentagon example, counting only the bounded interior would give \(F=1\), and then \(5-5+1=1\), not \(2\). The correction is to include the exterior region: \(F=2\), and \(5-5+2=2\).

The spanning-tree argument is useful because it turns face counting into an edge count. Start with one face and \(n-1\) tree edges; each of the \(m-n+1\) remaining edges contributes one face. This method also provides a practical check: if a proposed face count for a connected plane graph does not satisfy \(n-m+F=2\), at least one of the counts or the claimed embedding needs review.