Computing Face Counts from Euler's Formula

Using Euler’s Formula to Find a Missing Count

In a plane graph, vertices, edges, and faces are linked by an equation. When two of these counts are known, the third is determined. The calculation is short, but it depends on using the right graph and the right counts: the graph must be connected and embedded in the plane, and the face count includes the unbounded face.

Throughout this tutorial, graphs are finite and simple unless stated otherwise. A plane graph is a graph together with a particular drawing in the plane in which edges meet only at common endpoints. Its faces are the regions of the plane left after removing the drawing, including the unbounded region. Write \(V=|V(G)|\) for the number of vertices, \(E=|E(G)|\) for the number of edges, and \(F\) for the number of faces in the given plane embedding.

Rearranging the equation gives three ways to find a missing count. Use the form that isolates the unknown, then substitute the result back into the original equation. This substitution is a basic arithmetic check; it does not, by itself, prove that arbitrary supplied counts come from a particular plane embedding.

In each equation, the two counts on the right must belong to the same connected plane graph. If all three counts are supplied, the equation instead provides a consistency test: the counts must satisfy \(V-E+F=2\). Passing that numerical test is necessary, but without further information it does not certify a particular graph or embedding.

Finding the Number of Faces

To calculate \(F\), use \(F=2-V+E\). Be careful with the sign of \(V\): it is subtracted. A connected plane tree, for instance, has one face, and the formula will give that result because a tree on \(V\) vertices has \(E=V-1\). The examples below specify the graphs and their embeddings so that the inputs and checks are explicit.

The order of subtraction matters. In the example, \(2-5+4=1\), not \(2-4+5\). When working quickly, it is safer to write the general rearrangement first and then substitute each count in its place.

Finding an Edge or Vertex Count

The same formula can be rearranged to find \(E\) or \(V\). For the edge count, add \(E\) and subtract \(2\) from the original relation to obtain \(E=V+F-2\). For the vertex count, move \(F\) to the other side and add \(2\), giving \(V=E-F+2\). Keeping the original relation in view helps prevent sign errors.

Why the Missing Count Is Unique

The rearrangements are not separate formulas that give competing answers. Each is equivalent to the same equation. Consequently, once any two counts of a connected plane graph are fixed, there can be at most one value of the third count that satisfies Euler’s formula.

Proof. Assume \(V-E+F=2\). If \(V\) and \(E\) are fixed, subtract \(V\) from both sides and add \(E\) to both sides to obtain \(F=2-V+E\), so there is only one possible value of \(F\). If \(V\) and \(F\) are fixed, add \(E\) to both sides and subtract \(2\) to obtain \(E=V+F-2\), so there is only one possible value of \(E\). If \(E\) and \(F\) are fixed, add \(E\) to both sides and subtract \(F\) from both sides to obtain \(V=E-F+2\), so there is only one possible value of \(V\). These rearrangements also show that each displayed candidate satisfies the original equation. \(\square\)

A useful arithmetic consequence is that \(V+F\) and \(E\) have the same parity: they are either both even or both odd.

Proof. Starting from \(V-E+F=2\), add \(E\) to both sides to get \(V+F=E+2\). Since \(2\) is even, \(E+2\) and \(E\) have the same parity. Therefore \(V+F\) and \(E\) have the same parity. \(\square\)

This parity relation is a quick check on a proposed set of counts, but it is weaker than Euler’s formula: passing the parity check alone does not establish that the counts satisfy the full equation.

Checking Consistency and Avoiding Scope Errors

Suppose someone proposes \(V=5\), \(E=5\), and \(F=3\) for a connected plane graph. Substitution gives \(V-E+F=5-5+3=0+3=3\), not \(2\). These counts cannot belong to a connected plane graph. This is a useful diagnostic: it finds an inconsistency without needing to redraw the graph.

Do not use the connected formula automatically when the graph has more than one connected component. The hypothesis is not a technical detail; the corresponding formula for disconnected plane graphs differs. First establish that the graph is connected, or use the appropriate result for disconnected plane graphs from the earlier material.

Also distinguish a plane graph from a planar graph. A planar graph is one that can be drawn in the plane without crossings; a plane graph includes a particular such drawing. The face count \(F\) refers to that drawing. For a connected planar graph, Euler’s formula holds for any crossing-free plane embedding, but when counting faces in a problem, be sure to count regions in the stated embedding and include the unbounded one.

Common Pitfalls

Incorrect rearrangement. A frequent error is to write \(F=2+V-E\). The correct rearrangement is \(F=2-V+E\): from \(V-E+F=2\), subtract \(V\) and add \(E\) to both sides. For example, if \(V=5\) and \(E=4\), the correct calculation is \(F=2-5+4=1\), not \(2+5-4=3\). The corrected value checks because \(5-4+1=2\).

Dropping the unbounded face. In the convex pentagon example, there is one bounded region and one unbounded region, so \(F=2\), not \(1\). Omitting the unbounded face would give \(5-5+1=1\), which fails Euler’s formula.

Using the wrong hypotheses. Before calculating, check that the graph is connected and that the input \(F\) counts all regions of its plane embedding. If either condition fails, the connected-graph calculation may not apply as written.