Bridges and the Two Sides of an Edge
In a plane drawing, each edge has two local sides. For an edge on a cycle, the two sides lie on opposite sides of that cycle. A bridge behaves differently: its two sides are incident with the same face. The face boundary records this by traversing the bridge once in each direction. This can make a boundary walk repeat an edge, and it can also make vertices appear more than once.
All graphs below are finite and simple. A plane graph is a graph together with a fixed drawing in the plane in which edges meet only at common endpoints. A face is a connected component of the complement of the drawing. A face is incident with an edge side if points immediately beside that side belong to the face. The two sides are counted separately, even when they border the same face.
A boundary walk is a closed walk that traces the edge-sides around a face. An edge may occur more than once in a boundary walk, and vertices may repeat. When a boundary walk traverses an edge in a specified direction, that traversal is one directed occurrence of the edge. The walk's length counts occurrences, not distinct edges.
Tracing a Face Boundary
At each vertex of a plane graph, the incident edges have a cyclic order given by their arrangement around the vertex. To trace a face boundary, follow a directed edge to its endpoint; then, in the cyclic order at that endpoint, take the edge immediately next to the reverse of the edge just traversed. Fix one direction, such as clockwise, throughout. This rule follows the same face locally. Repeating it eventually closes a walk: each directed edge has exactly one successor and one predecessor, so the directed edges split into closed tracing walks. For a connected plane graph, these walks trace the face boundaries.
This description also explains why a boundary walk is not necessarily a cycle. A cycle has no repeated vertices apart from the matching start and end, whereas a boundary walk may revisit a vertex or traverse the same undirected edge in both directions.
Proof. Let \(e=uv\). If \(e\) lies on a cycle, the rest of that cycle is a \(u\)-to-\(v\) path not using \(e\). Deleting \(e\) therefore does not disconnect its endpoints, so it does not increase the number of components. Conversely, suppose \(e\) lies on no cycle. If deleting \(e\) did not disconnect its endpoints, there would be a \(u\)-to-\(v\) path avoiding \(e\). Removing any repeated sections gives a simple \(u\)-to-\(v\) path; together with \(e\), it forms a cycle. This contradicts the assumption that \(e\) lies on no cycle. Thus deleting \(e\) disconnects its endpoints, and \(e\) is a bridge. \(\square\)
Why Both Sides of a Bridge Border the Same Face
Proof. Let \(e=uv\) be a bridge, and let \(W\) be the facial boundary walk obtained by tracing the directed occurrence \(u\) to \(v\). Since deleting \(e\) separates the connected graph into a part containing \(u\) and a part containing \(v\), \(e\) is the only edge joining those two parts. The walk \(W\) is closed. After it crosses from the \(u\)-part to the \(v\)-part along \(u\) to \(v\), it must eventually return to its starting part before it closes. The only way to cross back is along \(v\) to \(u\). Thus the same boundary walk contains both directed occurrences of \(e\). Each occurrence traces one of the two local sides, so both sides border the face traced by \(W\). \(\square\)
The proof depends on the separation caused by deleting the bridge and on the fact that a facial tracing is closed. It does not say that every edge has both sides in the same face. For example, an edge on a cycle has a route around the rest of the cycle connecting its endpoints without using that edge; such an edge is not a bridge by the lemma.
Worked Example: A Three-Vertex Path
Let \(G\) have vertex set \(V=\{1,2,3\}\) and edge set \(E=\{12,23\}\), drawn as the path \(1-2-3\). Specify the cyclic orders of outgoing edges as follows: at \(1\), \([12]\); at \(2\), \([21,23]\); at \(3\), \([32]\). Each edge is a bridge: deleting \(12\) isolates \(1\), and deleting \(23\) isolates \(3\).
Start the face trace with the directed edge \(1\) to \(2\). At vertex \(2\), after the reverse edge \(21\), the next edge is \(23\). At vertex \(3\), the only next edge is \(32\). At vertex \(2\), after \(23\), the next edge is \(21\). At vertex \(1\), the trace returns along \(12\) and closes. The boundary walk is therefore \(1,2,3,2,1\), of length \(4\).
Check: the walk uses \(12\) in the directions \(1\) to \(2\) and \(2\) to \(1\), and uses \(23\) in the directions \(2\) to \(3\) and \(3\) to \(2\). Thus each edge has both sides incident with the face traced by this walk. The length is \(4=2+2\), counting two directed occurrences for each of the two edges.
Worked Example: A Triangle with a Pendant Bridge
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,31,14\}\). Draw the triangle \(1,2,3,1\) with edge \(14\) attached at vertex \(1\). The edge \(14\) is a bridge, since deleting it isolates vertex \(4\). Take these clockwise cyclic orders: at \(1\), \([12,14,13]\); at \(2\), \([21,23]\); at \(3\), \([32,31]\); at \(4\), \([41]\).
Trace the boundary beginning with \(1\) to \(4\). At \(4\), the next edge is \(41\). At \(1\), after the reverse edge \(14\), the next edge is \(13\). At \(3\), after \(31\), take \(32\); at \(2\), after \(23\), take \(21\); and at \(1\), after \(12\), take \(14\), which closes the walk. Its vertex sequence is \(1,4,1,3,2,1\), and its directed edge sequence is \(14,41,13,32,21\). In particular, the bridge is traversed in both directions, and vertex \(1\) occurs repeatedly.
The other boundary walk follows the triangle: \(12,23,31\), or vertex sequence \(1,2,3,1\). The first walk has length \(5\) and the second has length \(3\). Together they have \(5+3=8\) directed occurrences. There are \(4\) edges, so the total number of directed edge occurrences is \(2\cdot4=8\), as required. The two occurrences of \(14\) are in the same boundary walk, while the triangle edges each occur once in each of the two walks.
Worked Example: Two Triangles Joined by a Bridge
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,31,34,45,56,64\}\). Draw triangles \(1,2,3,1\) and \(4,5,6,4\), joined by edge \(34\). This edge is a bridge: deleting it separates the two triangles. Use the clockwise cyclic orders \([12,13]\) at \(1\), \([21,23]\) at \(2\), \([32,34,31]\) at \(3\), \([43,45,46]\) at \(4\), \([54,56]\) at \(5\), and \([65,64]\) at \(6\).
Tracing from \(12\), the successive directed edges are \(12,23,34,45,56,64,43,31\), and the next edge is \(12\). This boundary walk has length \(8\); it goes across the bridge \(34\) and later returns across \(43\). The other two boundary walks are \(13,32,21\) and \(46,65,54\), each of length \(3\). Thus the listed walks have total length \(8+3+3=14\). Since \(|E|=7\), counting both directions of every edge gives \(2|E|=2\cdot7=14\), matching the trace.
Check: edge \(34\) occurs twice in the length-\(8\) walk and not in either triangle boundary. Each of the other six edges occurs once in the length-\(8\) walk and once in its triangle's length-\(3\) walk. Hence all \(14\) directed occurrences are accounted for.
Common Pitfall: Counting a Bridge Only Once
A frequent error is to count a bridge as appearing only once on a face boundary because it is only one edge in the graph. In the path example, this would give a supposed boundary walk \(1,2,3\), which is not closed. The correct trace is \(1,2,3,2,1\): edge \(12\) appears in both directions, and edge \(23\) appears in both directions. The boundary length is \(4\), not \(2\). The edge itself has not been duplicated in the graph; its two sides are represented by two traversals in the boundary walk.
Repeated vertices should also not be mistaken for an error. A boundary walk is allowed to revisit a vertex, as the triangle-with-pendant example shows. What matters is that each step follows an edge and that the tracing rule closes the walk. Keeping directed occurrences distinct makes the accounting reliable: a bridge contributes two occurrences to one face boundary, even though those occurrences correspond to the same undirected edge.
Check Your Understanding
For each question, distinguish the graph's edges from their directed occurrences in a boundary walk.
- Let \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), drawn as a path. Which edges are bridges, and how many times does each occur in the traced face boundary?
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,14\}\), why is \(14\) a bridge while \(12\) is not?
- Explain why a closed facial boundary walk that crosses a bridge from one component of \(G-e\) to the other must later use the reverse direction of that edge.
- A connected plane graph has \(6\) edges. How many directed edge occurrences appear in the collection of all its face-boundary walks, counting repetitions?
- Give an example in which a face boundary walk repeats a vertex, and explain why this does not prevent the walk from being a valid boundary walk.