The Question: Does a New Edge Split a Face?
In a plane embedding, an edge can be drawn inside a face without crossing any existing edge. The endpoints must lie on the boundary of that face, but that alone does not determine whether the face count changes. The key question is whether those endpoints are already connected by a path in the graph. If they are, the new edge completes a cycle and splits the face. If they belong to different components, the new edge is a bridge and the face count stays the same.
We work with finite simple graphs embedded on the sphere. A face is a connected component of the complement of the embedded graph, and \(f(G)\) denotes the number of faces in the given embedding. A component means a connected component of the abstract graph: two vertices are in the same component exactly when a path joins them. An edge insertion means drawing one new edge \(uv\) so that its interior lies in a single face and meets the old graph only at its endpoints. The vertices \(u\) and \(v\) are distinct, and \(uv\) is not already an edge, so the graph remains simple.
We use the sphere so that there is no special status for an unbounded face. The conclusions are the same in a plane drawing: the unbounded region is simply one of the faces. Boundary walks may repeat vertices or edges, especially around bridges. Thus, an endpoint can occur more than once on a face boundary; the component test concerns the vertices themselves, not the number of boundary occurrences.
Why the Component Test Works
Proof. Consider first the case in which \(u\) and \(v\) are in the same component. There is a path in \(G\) from \(u\) to \(v\); choose one with no repeated vertices. Together with the new edge \(uv\), this path forms a cycle. The new edge is on a simple closed curve, which separates the sphere into two sides by the Jordan curve theorem. Since the interior of \(uv\) lies in \(F\), the new edge divides that face into two faces. No other face changes: the drawing outside \(F\) is untouched, and the new edge has no interior point outside \(F\). Therefore the net change is exactly one face.
Now suppose \(u\) and \(v\) are in different components. After inserting \(uv\), removing that edge separates \(u\) from \(v\) again, so \(uv\) is a bridge of the resulting graph. The bridge-face fact from the earlier material on bridges and repeated face boundaries says that both sides of a bridge are incident with the same face. Thus this insertion does not split \(F\). All other faces are unchanged, so \(f\) stays the same. The two cases cover all possibilities for \(u\) and \(v\), proving the theorem. \(\square\)
The proof also explains why the bridge case is different from merely adding an edge to a tree. A new edge that joins two components may increase the graph’s connectivity while leaving the number of faces unchanged. Conversely, an edge that joins vertices already connected by a path creates a cycle, and that cycle separates the sphere.
Worked Insertions
Worked Example: Closing a Path
Let \(G\) have vertex set \(V=\{a,b,c,d\}\) and edge set \(E=\{ab,bc,cd\}\), embedded as a path. Insert \(ad\) by an arc in the face, with no intersections with the path except at \(a\) and \(d\).
The graph is connected, so \(a\) and \(d\) are in the same component. The path \(a,b,c,d\) has length \(3\). Adding \(ad\) completes the cycle \(a,b,c,d,a\), which bounds a region on the sphere. Before insertion the embedded path has one face: the complement of a tree embedded on the sphere is connected. After insertion the cycle has two faces, one on each side. Hence the face count changes from \(1\) to \(2\), giving \(2-1=1\).
Check: the new edge lies on the displayed cycle, so its two sides belong to the two different regions bounded by that cycle. This agrees with the theorem’s same-component case.
Worked Example: Joining Two Isolated Vertices
Let \(G\) have vertex set \(V=\{x,y\}\) and edge set \(E=\varnothing\), with \(x\) and \(y\) drawn as distinct points on the sphere. Draw the new edge \(xy\) as a simple arc between them.
Before insertion, the graph has two components, \(\{x\}\) and \(\{y\}\). Its complement is connected, so \(f(G)=1\). After insertion, the graph consists of one arc. Its complement is still connected, so the new face count is also \(1\). Thus the change is \(1-1=0\).
Check: deleting \(xy\) from the resulting graph disconnects \(x\) from \(y\), so \(xy\) is a bridge. It has the same face on both sides and does not create a cycle.
Worked Example: A Bridge Inside a Bounded Face
Let \(G\) have vertices \(V=\{a,b,c,d,x\}\) and edges \(E=\{ab,bc,cd,da\}\). Embed the four-cycle \(a,b,c,d,a\) as the boundary of a square, and place the isolated vertex \(x\) strictly inside the square. There are two faces: the square’s interior and its exterior, so \(f(G)=2\).
Insert the edge \(ax\) as an arc inside the square. Before insertion, \(a\) and \(x\) are in different components: one is on the four-cycle, and the other is isolated. The new edge is therefore a bridge. The exterior face remains unchanged, and the square’s interior remains a single face with the bridge drawn inside it. Consequently the face count after insertion is \(2\), and its change is \(2-2=0\).
Check: \(ax\) does not close a cycle, because removing it leaves \(x\) isolated. The fact that the edge is drawn inside a bounded face does not make that face split.
Worked Example: Inserting Edges in Sequence
Start with the graph \(G_0\) on \(V=\{a,b,c,d\}\) and \(E=\{ab,bc\}\). Embed it as a path \(a,b,c\) and an isolated vertex \(d\), positioned so the following insertions can be drawn in the indicated faces without crossings. Initially there is one face: \(f(G_0)=1\).
First insert \(cd\). Its endpoints are in different components, so it is a bridge and does not change the face count: \(f(G_1)=1\). The graph \(G_1\) is now the path \(a,b,c,d\), hence connected. Next insert \(ad\) along an arc in its face. Its endpoints are in the same component, and \(a,b,c,d,a\) is the resulting cycle. This insertion adds one face: \(f(G_2)=1+1=2\).
Check: the first insertion joined two components and created no cycle. The second closed the four-edge path into a cycle and split the face. The final drawing has that cycle’s two sides as its two faces.
Counting Several Insertions
The theorem applies successively, but the component test must be made in the graph at the time each edge is inserted. Earlier insertions can change which vertices are connected. If \(k\) edges are inserted in sequence, and \(s\) of those insertions have endpoints in the same component immediately before insertion, then
Indeed, each of the \(k\) insertions changes the face count by either \(1\) or \(0\), according to the theorem. Summing those changes gives one for each of the \(s\) same-component insertions and zero for every other insertion. This count assumes each edge can be drawn in a single face with its interior avoiding the existing graph, and that the graph stays simple.
This is not a rule that depends only on the number of edges added. In the sequential example, two edges were added but only one new face appeared. The order matters for the component test: after an edge joins two components, a later edge between vertices in the joined component may close a cycle.
Common Pitfall: Every New Edge Does Not Add a Face
A tempting but incorrect calculation is to say, “One edge was added, so the face count increases by one.” For the two isolated vertices in the second example, that calculation would give \(f=1+1=2\). But the inserted edge is a bridge, and its two sides are incident with the same face; the correct count is \(f=1+0=1\).
The opposite shortcut is also unreliable: an edge is not automatically a bridge just because it is drawn inside one face. In the first example, \(ad\) is drawn inside the sole face, but its endpoints were already connected. The new edge completes a cycle and increases the face count from \(1\) to \(2\). Always test whether the endpoints are already in the same component before insertion.
Check Your Understanding
For each question, use the component test before counting the faces.
- A plane graph has one component, and a new edge is drawn inside a face between two nonadjacent vertices. What condition ensures that this insertion adds one face?
- Two isolated vertices are joined by an edge on the sphere. State the change in face count and explain why the edge is a bridge.
- A cycle has an isolated vertex inside its bounded face. An edge is drawn from that vertex to a cycle vertex. Does the bounded face split? Explain.
- Three edges are inserted successively. Two insertions join different components at the time they are made, and one joins vertices in the same component. What is the total change in the number of faces?
- Why is it insufficient to know only that both endpoints of a new edge occur on the boundary walk of the same face?