Euler's Formula for Disconnected Plane Graphs

Why the Connected Formula Needs an Adjustment

For a connected plane graph, Euler’s formula is $V-E+F=2$. A disconnected plane graph has additional components, and each one changes the relation between vertices, edges and faces. The correct adjustment depends on the number of components, not on how many of them contain edges. In particular, an isolated vertex is a component and must be counted.

Throughout, graphs are finite and simple. A plane graph is a graph together with a particular drawing on the sphere in which edges meet only at common endpoints. A face is a connected component of the complement of that drawing. Counting faces on the sphere is equivalent to counting faces in the plane, with the unbounded region included. The number of components $C$ refers to connected components of the graph, including isolated vertices.

Theorem: If a plane graph has $V$ vertices, $E$ edges, $F$ faces and $C$ connected components, then $$ V-E+F=C+1. $$ Here the empty graph has $V=E=C=0$ and one face, so the formula includes that case.

The proof will use a spanning forest. This is a subgraph containing every vertex, with one tree spanning each component of the original graph. A component consisting of an isolated vertex contributes a one-vertex tree. The forest lets us begin with all the vertices and components present, but with no cycles. We then restore the edges not in the forest and track the faces they create.

What a Spanning Forest Contributes

First consider a plane forest, meaning a plane graph with no cycles. If it has $V$ vertices and $C$ components, it has $V-C$ edges. Indeed, each component is a tree: a tree on $k$ vertices has $k-1$ edges, including the one-vertex case $k=1$, which has zero edges. Summing over the $C$ components gives $V-C$ edges in total.

Lemma: A plane forest with at least one vertex has exactly one face.

Proof. Every edge of a forest is a bridge: deleting it disconnects the tree component containing it. Remove the forest’s edges one at a time. At each removal, the edge is a bridge, and deleting a bridge from a plane graph does not change the face count: the two sides of the bridge already belong to the same face. When all edges have been removed, only finitely many isolated points remain. The sphere with finitely many points removed is connected, so this drawing has one face. Therefore the original forest also had one face. $\square$

For the empty forest there are no vertices or edges, and the complement of its drawing is the whole sphere, which is also one face. Thus in either case the starting face count is one.

We also need the effect of restoring a nonforest edge. The edge-insertion rule from the earlier material on how edge insertion changes face counts says that adding an edge whose endpoints are already connected increases the number of faces by one. To see why the condition matters, take a simple path already joining the endpoints. The new edge’s interior lies in one face and does not meet the path. Together, the path and the new edge form a simple closed curve, which separates the sphere and splits that face into two. Thus the face count increases by exactly one.

Proof by Restoring the Edges

Proof of the theorem. First suppose the graph has at least one vertex, and choose a spanning forest $T$. It has the same $V$ vertices and $C$ components as the graph. By the tree edge count, $T$ has $V-C$ edges. By the lemma, its plane drawing has one face.

Now restore the edges of the original graph that are not in $T$, using their original locations in the plane embedding. Each such edge has endpoints in the same component of the original graph. The spanning tree of that component already joins those endpoints, and all the edges of that tree remain present as we restore edges. Consequently, the endpoints are already connected at the moment each edge is inserted. By the edge-insertion rule, each restored edge increases the face count by one.

The number of restored edges is $E-(V-C)$. Starting with one face, we therefore obtain

F=1+\bigl(E-(V-C)\bigr)=1+E-V+C.

Rearranging gives $V-E+F=C+1$. If the graph is empty, its drawing has one face and $V=E=C=0$, so $0-0+1=0+1$ as well. This proves the formula in all cases. $\square$

Worked Example: A Triangle and an Isolated Vertex

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,31\}$. Embed $1,2,3$ as the vertices of a triangle and place vertex $4$ away from it. The graph has two components: the triangle and the isolated vertex.

Choose the spanning forest with edges $12,23$, together with all four vertices. It has $V-C=4-2=2$ edges and one face. The remaining edge $31$ joins vertices already connected in the forest, so inserting it splits a face and gives $F=1+1=2$.

Now check the formula using the counts: $V=4$, $E=3$, $F=2$, and $C=2$. Hence $V-E+F=4-3+2=3$, while $C+1=2+1=3$. Independently, the triangle separates the sphere into its interior and exterior, and the isolated point does not divide either region. There are exactly two faces.

Worked Example: Two Disjoint Cycles

Let $G$ have vertex set $V=\{1,2,3,4,5,6,7\}$ and edge set $E=\{12,23,34,41,56,67,75\}$. Embed the 4-cycle $1,2,3,4,1$ and the triangle $5,6,7,5$ as disjoint polygons, separated from one another. There are $C=2$ components.

Choose forest edges $12,23,34$ in the 4-cycle and $56,67$ in the triangle. The forest has $3+2=5$ edges, which agrees with $V-C=7-2=5$, and it has one face. The two omitted edges are $41$ and $75$. Each closes a cycle within its own component, so each insertion increases the face count by one. Thus $F=1+2=3$.

Substitution gives $V-E+F=7-7+3=3$, and $C+1=2+1=3$. For an independent face count, the two disjoint polygon boundaries have two separate interiors and one common exterior region on the sphere, giving three faces.

Worked Example: A Plane Forest with Isolated Vertices

Let $G$ have vertex set $V=\{1,2,3,4,5,6\}$ and edge set $E=\{12,23,45\}$. Its components are the path $1,2,3$, the edge $45$, and the isolated vertex $6$, so $C=3$.

This graph is already a spanning forest. Its edge count is $3$, matching $V-C=6-3=3$, and its face count is $F=1$ by the lemma. The formula gives $V-E+F=6-3+1=4$, while $C+1=3+1=4$. Counting components explicitly is essential here: the isolated vertex contributes one to $C$, despite contributing no edge.

How to Use the Formula Reliably

For a disconnected plane graph, the right-hand side is determined by the number of connected components. Once three of $V,E,F,C$ are known, the formula determines the fourth. For example, if $V=9$, $E=8$, and $C=3$, then $F=C+1-V+E=3+1-9+8=3$. This is an application of the formula; to verify a particular drawing, one can also inspect its regions or use the spanning-forest argument.

The forest proof explains why the component count appears. A forest on $V$ vertices with $C$ components has $V-C$ edges, not $V-1$. The remaining $E-(V-C)$ edges each close a connection already present in the forest and each add one face. The initial one face and these additional faces give $F=1+E-V+C$.

Common Mistake: Forgetting Isolated Components

A common error is to use the connected formula $V-E+F=2$ for a graph with several components, or to count only components that contain edges. In the first example, the triangle plus an isolated vertex has $V=4$, $E=3$, and $F=2$, so $V-E+F=4-3+2=3$, not $2$. Its component count is $C=2$, and the correct right-hand side is $C+1=2+1=3$. The isolated vertex contributes no edge and does not create a face, but it is still a component.

For the empty graph, use the same convention consistently: $C=0$, and the sphere minus the empty drawing has one face. Therefore $V-E+F=0-0+1=1=C+1$. Treating the empty graph as though it had one component would instead give the wrong result.

Check Your Understanding

For each question, state the component count explicitly, including isolated vertices.

A plane graph has $V=8$, $E=7$, and $C=3$. Use Euler’s formula to find $F$.
Why does a spanning forest of a graph with $V$ vertices and $C$ components have $V-C$ edges?
A plane forest has five vertices and two components. How many edges and faces does it have? Explain both counts.
For a plane graph consisting of two disjoint triangles, embedded as separate polygons, count the faces directly and verify Euler’s formula.
What are $V,E,F,C$ for the empty graph under the conventions used here, and does the formula hold?