What a Face Count Is Counting
Euler’s formula is a useful check on a plane graph, but only when its quantities are counted consistently. A frequent source of errors is to count only the bounded faces. Another is to treat each appearance of an edge along a face boundary as a new graph edge. Bridges cause particular confusion: a bridge is one edge, but its two sides border the same face, so it occurs twice in that face’s boundary walk.
A plane graph is a graph drawn in the plane with vertices at distinct points and edges represented by arcs that meet only at common endpoints. A face is a connected region of the plane left after the drawing is removed. Exactly one face is unbounded; all other faces are bounded. A facial boundary walk traces the edges and vertices encountered while following the boundary of a face. A boundary walk may repeat vertices and edges, so its length counts edge appearances, not distinct edges.
For example, when following the boundary of a face, one occurrence of an edge corresponds to one of its sides. The two sides can border different faces, or both can border the same face. The second situation occurs for a bridge: deleting that edge disconnects its endpoints, and there is no cycle around it separating one side from the other. Its two sides are therefore incident with the same face.
For a connected plane graph with \(n\) vertices, \(m\) edges and \(f\) faces, Euler’s formula is \(n-m+f=2\). This is Euler’s formula for connected plane graphs, established earlier in the course. The count \(f\) includes the unbounded face. The formula does not say that the number of bounded faces is \(2-n+m\); rather, that expression gives the total number of faces, including the unbounded one.
Counting Edge-Side Occurrences
Proof. Consider the two sides of every edge in the drawing. Each side is incident with a face, so it contributes one occurrence to the boundary of that face. If the two sides border different faces, the edge contributes one occurrence to each of two boundary lengths. If both sides border the same face, it contributes two occurrences to that one boundary length. In either case, the edge contributes exactly two occurrences to the sum over all faces. Summing over the \(m\) distinct edges gives \(2m\). \(\square\)
This lemma gives a useful audit: add the lengths of all facial boundary walks, including the unbounded face and repeated traversals of bridges. The total must be \(2m\). It also explains why adding the lengths does not usually give the number of edges: each edge has two sides, and both sides are counted.
Worked Examples: Spotting the Common Errors
Worked Example: Omitting the Unbounded Face
Take the plane triangle \(G=(V,E)\), where \(V=\{1,2,3\}\), \(E=\{12,23,31\}\), and the edges are drawn as the sides of a triangle. Find the total number of faces and check Euler’s formula.
The drawing has one bounded face, the triangular interior, and one unbounded face, the exterior. Thus \(n=3\), \(m=3\), and \(f=2\). Substitution gives \(n-m+f=3-3+2=2\), as required.
A mistaken calculation that counts only the bounded face sets \(f=1\). It then gives \(3-3+1=1\), not \(2\). The arithmetic is correct; the input is wrong because the unbounded face has been omitted.
Check: the bounded face has boundary length \(3\), and the unbounded face also has boundary length \(3\). Their total is \(3+3=6\). There are \(m=3\) edges, so \(2m=2\cdot3=6\), agreeing with the edge-side count.
Worked Example: A Bridge Appears Twice
Let \(G=(V,E)\), where \(V=\{1,2,3\}\) and \(E=\{12,23\}\), drawn as the path \(1-2-3\). Both edges are bridges. Determine the face boundary and check the counts.
The drawing has one face, the unbounded face. Tracing its boundary gives the closed walk \(1,2,3,2,1\). Edge \(12\) appears twice, and edge \(23\) appears twice. The boundary length is therefore \(4\), although the graph has only \(m=2\) distinct edges. With \(n=3\) and \(f=1\), Euler’s formula gives \(3-2+1=2\).
A common wrong count calls the boundary length \(4\) the number of edges. That would replace \(m=2\) by \(m=4\), giving \(3-4+1=0\), which fails Euler’s formula. The correction is to count the distinct edges once in \(m\), while retaining both appearances in the boundary walk.
Check: the single face has boundary length \(4\). The two edges contribute \(2\cdot2=4\) edge-side occurrences in total, so the lemma’s count agrees. The graph has \(m=2\), not \(4\).
Worked Example: A Triangle with a Pendant Edge
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,14\}\). Draw \(1,2,3\) as a triangle and draw the edge \(14\) outward from vertex \(1\), with no crossings. Find the facial boundary lengths.
The bounded face is the triangle, with boundary walk \(1,2,3,1\) and length \(3\). The unbounded face has boundary walk \(1,2,3,1,4,1\), of length \(5\). In that outer walk the pendant edge \(14\) is traversed once from \(1\) to \(4\), then again from \(4\) to \(1\). Thus \(n=4\), \(m=4\), and \(f=2\), so Euler’s formula gives \(4-4+2=2\).
The boundary lengths sum to \(3+5=8\). This does not mean there are eight edges. The graph has four distinct edges. Each triangle edge contributes one occurrence to the bounded face and one to the unbounded face, while the bridge contributes two occurrences to the unbounded face.
Check: the edge-side total is \(2m=2\cdot4=8\), matching \(3+5=8\). The bridge \(14\) is counted once in \(m\) and twice in the outer boundary length.
Worked Example: Repeated Edge Occurrences Are Not New Edges
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\). Draw the 4-cycle \(1,2,3,4,1\) as a square and draw diagonal \(13\) inside it. List the face boundaries and audit the count.
There are two bounded triangular faces, with boundary walks \(1,2,3,1\) and \(1,3,4,1\), each of length \(3\). The unbounded face has boundary walk \(1,2,3,4,1\), of length \(4\). Hence \(f=3\), including the exterior face. The size is \(m=5\): the four sides of the square and one diagonal.
The sum of boundary lengths is \(3+3+4=10\), while the graph has five distinct edges. If one incorrectly treats all ten boundary occurrences as distinct edges, then \(n-m+f\) would be \(4-10+3=-3\), not \(2\). The correction is that each occurrence records a side of an edge, not a newly created edge.
Check: substituting the actual vertex, edge and face counts gives \(4-5+3=2\). Independently, the face-boundary lengths total \(10\), and \(2m=2\cdot5=10\). Both checks agree.
A Practical Audit
When a face count seems inconsistent, do not immediately change the drawing or the formula. Check what each quantity represents. For a connected plane graph, the audit can be carried out in a fixed order:
Record \(n=|V|\) and \(m=|E|\). Each edge is counted once, regardless of how many facial boundary walks contain it or how many times it occurs on one walk.
Include the unbounded face. A face is a region of the plane, not a cycle, and its boundary walk need not be a cycle.
When a bridge is encountered on a face boundary, follow both of its sides. The bridge may appear twice in that same facial boundary walk.
For a connected plane graph, verify \(n-m+f=2\). Separately add the face-boundary lengths and verify that their sum is \(2m\).
These checks detect different mistakes. Euler’s formula can expose an omitted face or an incorrect count of distinct edges. The edge-side sum checks whether boundary traversals have been recorded consistently. Passing one check is not a substitute for defining the quantities correctly: an accidental pair of errors can sometimes cancel in a calculation.
Common Mistakes and Their Corrections
- Using only bounded faces. In Euler’s formula, \(f\) counts all faces, including the unbounded face. In the triangle example, using \(f=1\) instead of \(f=2\) changes the left side from \(2\) to \(1\).
- Counting a bridge only once on its face boundary. A bridge has two sides, both incident with the same face. Its boundary walk therefore uses that edge twice, though the edge contributes only once to \(m\).
- Calling the total boundary length the edge count. The sum over faces is \(2m\), not \(m\), because every edge has two sides. A boundary walk may also repeat the same edge within one face.
- Assuming each face boundary is a cycle. A boundary walk can repeat an edge or a vertex. In the path example the only boundary walk is \(1,2,3,2,1\), which repeats both edges and vertex \(2\).
The central distinction is between a region, a boundary traversal, and a graph edge. The number of faces counts regions. A boundary length counts edge-side occurrences along a traversal. The size \(m\) counts distinct edges. Keeping those three counts separate makes Euler’s formula a reliable diagnostic rather than a source of conflicting numbers.
Check Your Understanding
For each question, distinguish carefully between a face, a boundary occurrence, and a distinct edge.
- A connected plane graph has \(n=5\) vertices and \(m=6\) edges. How many faces must it have? Does this count include the unbounded face?
- In the plane path with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), how many faces are there, and what is the length of the unbounded face’s boundary walk?
- Explain why a bridge contributes two occurrences to the sum of facial boundary lengths but only one to \(m\).
- A connected plane graph has face-boundary lengths \(3,4,5\). What value of \(m\) is required by the edge-side count? State the equation used.
- A calculation gives \(n=4\), \(m=5\), and \(f=2\) for a connected plane graph. Use Euler’s formula to determine whether these counts can all be correct.