From an Embedding to Its Faces
Euler’s formula relates vertices, edges and faces, but an explicit embedding gives more information than the total number of faces: it lets us trace the boundary walks that surround them. Doing this carefully reveals repeated edges, bridges and cases where one face has more than one boundary walk. These details are also useful checks on a face count obtained from Euler’s formula.
A plane embedding places vertices in the plane and represents each edge by a curve joining its endpoints, with edge interiors disjoint from one another and from all vertices. The faces are the connected regions of the plane left after removing the embedded graph; the unbounded region is the outer face. A graph is planar if it has a plane embedding. Throughout, the examples specify straight-line edges by giving vertex coordinates and an edge list.
To trace boundaries, treat each undirected edge \(uv\) as having two directed versions, \(u\to v\) and \(v\to u\), called its darts. At each vertex, the embedding gives a cyclic order of the incident edges. Start with a dart \(u\to v\). At \(v\), locate the edge back toward \(u\), then take the next edge clockwise in the cyclic order. This gives the next dart of the same facial boundary walk, with the face on the left as the walk is followed. Repeat until the starting dart returns.
The clockwise order is read locally around a vertex; its starting point in a written cyclic list is arbitrary. If a vertex has degree one, its only incident edge is also the next edge after itself, so a walk arriving along a pendant edge goes straight back along that edge. This is why a bridge can occur twice in one facial boundary walk.
Why the Incidence Count Works
Proof. Each edge has two sides, which correspond to its two darts. The tracing rule assigns each dart to exactly one facial boundary walk: after a dart is followed, the cyclic order at its endpoint determines exactly one next dart. Conversely, each step of a boundary walk follows one dart. Thus counting all steps across all boundary walks counts every dart exactly once. Since each of the \(m\) edges has two darts, the total length is \(2m\). This counts edge-sides, not distinct edges on a boundary, so a bridge whose two sides border the same face contributes twice. \(\square\)
For a connected plane graph, Euler’s formula is \(n-m+f=2\), where \(f\) is the number of faces. For a plane graph with \(c\) connected components, the formula is \(n-m+f=1+c\). These formulas give a useful independent check, but they do not replace tracing: tracing identifies which boundary walks belong to which faces.
Tracing and Auditing Examples
Worked Example: A Square with a Diagonal
Place vertices at \(1=(0,0)\), \(2=(2,0)\), \(3=(2,2)\), and \(4=(0,2)\). Draw each listed edge as a straight segment, with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\). The clockwise neighbor orders, written cyclically, are \(1:[4,3,2]\), \(2:[1,3]\), \(3:[2,1,4]\), and \(4:[3,1]\).
Apply the successor rule to the starting dart \(1\to2\). At \(2\), the next clockwise edge after the reverse edge toward \(1\) goes to \(3\); at \(3\), the next after the reverse edge toward \(2\) goes to \(1\); at \(1\), the next after the reverse edge toward \(3\) returns to \(2\). The resulting walk is \(1,2,3,1\). The other facial walks are obtained by continuing the same rule from an unvisited dart:
| Starting dart | Successive darts | Boundary walk | Length |
|---|---|---|---|
| \(1\to2\) | \(1\to2,2\to3,3\to1\) | \(1,2,3,1\) | 3 |
| \(1\to3\) | \(1\to3,3\to4,4\to1\) | \(1,3,4,1\) | 3 |
| \(1\to4\) | \(1\to4,4\to3,3\to2,2\to1\) | \(1,4,3,2,1\) | 4 |
The first two walks bound the two triangular faces; the last bounds the outer face. The total boundary length is \(3+3+4=10\), and \(2m=2\cdot5=10\). Also \(n-m+f=4-5+3=2\), as required for a connected plane graph.
Check: the edges \(12,23,34,41\) each occur once in an inner boundary and once in the outer boundary. The diagonal \(13\) occurs once in each triangular boundary. Thus the five edges contribute \(5\cdot2=10\) edge-side incidences.
Worked Example: A Bridge Appears Twice
Place vertices at \(1=(0,0)\), \(2=(2,0)\), \(3=(1,1)\), and \(4=(1,2)\), and draw straight edges with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\). Edge \(34\) is a bridge: deleting it separates vertex \(4\) from the triangle. The clockwise order at \(3\) is \([2,1,4]\); the other vertices have degree two or one.
Starting with \(1\to2\), the successor rule gives \(2\to3\), then \(3\to1\), and closes at \(1\to2\). This is the triangular boundary \(1,2,3,1\). Starting with \(1\to3\), the rule gives \(3\to4\), then \(4\to3\), then \(3\to2\), then \(2\to1\), and closes at \(1\to3\). The other boundary walk is \(1,3,4,3,2,1\). Its repeated edge \(34\) is not an error: the walk uses both darts of that bridge.
The lengths are \(3\) and \(5\), so the total is \(3+5=8\). Independently, \(m=4\), and \(2m=2\cdot4=8\). There are two faces, and \(n-m+f=4-4+2=2\). The bridge does not create an additional face.
Check: \(12,23,31\) each appear twice across the two walks, once for each side of the edge. Edge \(34\) appears twice in the second walk. The total is therefore \(3\cdot2+2=8\) incidences.
Worked Example: One Outer Face, Two Boundary Walks
Place two disjoint triangles far apart: vertices \(1=(0,0)\), \(2=(2,0)\), \(3=(1,1)\), and \(4=(5,0)\), \(5=(7,0)\), \(6=(6,1)\). Draw straight edges with \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,45,56,64\}\). Each triangle has one bounded face. Its other boundary walk borders the unbounded face.
Tracing the darts gives four boundary walks: \(1,2,3,1\) and \(1,3,2,1\) around the first triangle; \(4,5,6,4\) and \(4,6,5,4\) around the second. The two walks \(1,3,2,1\) and \(4,6,5,4\) belong to the same unbounded face, so there are four boundary walks but only three faces.
Each walk has length \(3\), giving total length \(3+3+3+3=12\). Since \(m=6\), \(2m=2\cdot6=12\). There are \(n=6\) vertices and \(c=2\) components, so the disconnected Euler check gives \(n-m+f=6-6+3=3=1+2=1+c\).
Check: each triangle has three edges, and each of its edges contributes two darts. The two triangles therefore contribute \(2\cdot(3\cdot2)=12\) incidences, matching the traced total.
Common Pitfalls and a Reliable Audit
A common mistake is to count an edge only once because it is geometrically one segment. For the square-with-diagonal example, that mistake would give a total of \(m=5\), while the traced face lengths add to \(10\). The correction is to count the two sides separately: the incidence total is \(2m=2\cdot5=10\), even when both sides of an edge border the same face.
Another mistake is to equate the number of boundary walks with the number of faces. In the disconnected example there are four boundary walks but three faces, because the two outer boundary components border the same unbounded region. Conversely, a walk that repeats a vertex or an edge should not automatically be discarded: such repetition can be required to trace the boundary of a face, as the bridge example shows.
For a careful audit of an explicit embedding:
- Specify the vertex set, edge set, and how the edges are drawn. Confirm that edge interiors do not cross.
- Read the clockwise cyclic order of incident edges at each vertex.
- Trace the successor of each dart, continuing until the starting dart returns; ensure every dart is used once.
- Group boundary walks by the face they border, paying special attention to the unbounded face when the graph is disconnected.
- Add the boundary lengths and check that the total is \(2m\). Count faces, then check \(n-m+f=2\) if connected or \(n-m+f=1+c\) if there are \(c\) components.
Euler’s formula is a consistency check, not a substitute for the embedding data. A numerical face count can satisfy Euler’s formula even when a proposed boundary walk is traced incorrectly. Checking both the local successor rule and the global counts makes the audit more dependable.
Check Your Understanding
For each question, state the edge-side count explicitly and distinguish boundary walks from faces when needed.
- In the square-with-diagonal example, how many times does dart \(3\to1\) occur among the facial boundary walks?
- Why does the bridge \(34\) appear twice in the boundary walk \(1,3,4,3,2,1\)?
- A connected plane graph has \(n=7\) and \(m=9\). What face count does Euler’s formula require, and what total boundary length must a trace produce?
- For the two disjoint triangles, explain why four boundary walks correspond to only three faces.
- What is wrong with the claim that the total length of facial boundary walks always equals \(m\)?