Edge-Face Incidences and Boundary Length

Counting Edge Sides

In a plane graph, an edge can appear more than once among the boundaries of faces. Counting only distinct edges on each boundary can therefore give the wrong total. The reliable count starts with the two local sides of every edge: each side borders a face, and each is counted as one boundary occurrence. The two sides may border different faces or the same face.

Throughout, a plane graph means a graph together with a fixed drawing in the plane in which vertices are distinct points and edges are arcs meeting only at common endpoints. A face is a connected region of the plane outside the drawing; the unbounded region is also a face. We use the boundary walks of a face as in the earlier material on faces and boundary walks. A walk records each traversal of an edge, so a boundary walk need not be a cycle.

Definition: An edge-side incidence is one of the two local sides of an edge in a plane embedding, together with the face bordering that side. The boundary length of a face $F$, written $\ell(F)$, is the total number of edge traversals in its boundary walks, counted with multiplicity. If an edge occurs twice in those walks, it contributes $2$, not $1$. For a plane graph with face set $\mathcal{F}$, the total boundary length is $\sum_{F\in\mathcal{F}}\ell(F)$.

At an interior point of an embedded edge, a sufficiently small neighborhood is divided by the edge into two sides. Following either side along the edge identifies the face bordering it. The face may be the same on both sides. For boundary counting, it is the two sides that matter, not whether their face labels agree.

The Edge-Side Count

Lemma: In a plane graph, boundary traversals are in one-to-one correspondence with edge-side incidences. In particular, each edge contributes exactly two boundary traversals, counted with multiplicity.

Proof. Assume a finite plane graph with its fixed embedding. Take any edge $e=uv$. Its interior has two sides. Trace the boundary of the face along one side of $e$; this records one traversal of $e$, in one of the directions $u$ to $v$ or $v$ to $u$. Tracing along the other side records the opposite directed traversal. Thus the two sides give two boundary occurrences, whether they border distinct faces or one face.

This accounts for every boundary traversal: a traversal follows an edge with a particular face on one side, so it specifies an edge-side incidence. Conversely, following the boundary of the face along that incidence gives the corresponding traversal. These correspondences are inverse, because the edge and the side being followed determine the traversal. Hence every edge-side incidence is counted exactly once among all face boundaries. Since each edge has two sides, it contributes exactly two traversals in total. $\square$

Theorem: For every finite plane graph $G=(V,E)$, the sum of the boundary lengths of its faces is twice its number of edges: $$ \sum_{F\in\mathcal{F}}\ell(F)=2|E|. $$

Proof. Count all boundary traversals in two ways. Grouping them by face gives $\sum_{F\in\mathcal{F}}\ell(F)$, by the definition of boundary length. Grouping them by the edge-side incidence that produces each traversal gives two contributions for each edge, by the Lemma. There are $|E|$ edges, so this second count is $2|E|$. The counts refer to the same set of traversals, and therefore $\sum_{F\in\mathcal{F}}\ell(F)=2|E|$. If $E=\varnothing$, there are no edge-side incidences and no boundary traversals, so both sides of the equality are $0$. $\square$

The theorem counts traversals rather than distinct edges in a face boundary. For example, if both sides of one edge border the same face, that face receives two occurrences from the edge. If the sides border two different faces, each of those faces receives one occurrence.

Worked Examples

Worked Example: A Plane 4-Cycle

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,34,41\}$. Embed it as a square in the plane, with edges drawn along the four sides of the square.

There are two faces: the bounded interior face and the unbounded exterior face. The interior boundary walk is $1,2,3,4,1$, so its length is $4$. The exterior boundary walk traverses the square in the opposite direction, $1,4,3,2,1$, also of length $4$. Thus the total boundary length is $4+4=8$. The graph has $|E|=4$, so $2|E|=2\cdot4=8$, agreeing with the theorem.

Each edge occurs once on the interior boundary and once on the exterior boundary. There are $4\cdot2=8$ such occurrences in total, an independent count that matches the two boundary walks.

Worked Example: A Plane Embedding of K4

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,31,14,24,34\}$. Draw $1,2,3$ as an outer triangle, put $4$ inside it, and draw the three edges from $4$ to $1,2,3$ without crossings.

The faces have boundary walks $1,2,3,1$, $1,2,4,1$, $2,3,4,2$, and $3,1,4,3$. Each has length $3$, so their total boundary length is $3+3+3+3=12$. There are six edges, and the theorem gives $2|E|=2\cdot6=12$.

Check by listing the two boundary occurrences of each edge: $12$ occurs on $1231$ and $1241$; $23$ on $1231$ and $2342$; $31$ on $1231$ and $3143$; $14$ on $1241$ and $3143$; $24$ on $1241$ and $2342$; and $34$ on $2342$ and $3143$. This gives $6\cdot2=12$ occurrences, independently confirming the face-by-face total.

Worked Example: One Edge, One Face

Let $G$ have vertex set $V=\{1,2\}$ and edge set $E=\{12\}$, drawn as a straight segment. The complement of this drawing in the plane has one face, the unbounded face. Both sides of the edge border that same face.

The boundary of the face traverses the edge once from $1$ to $2$ and once from $2$ to $1$, giving the boundary walk $1,2,1$ of length $2$. Therefore the total boundary length is $2$. The edge count gives $2|E|=2\cdot1=2$, as required.

There is one distinct edge in the drawing but two boundary traversals. Counting distinct edges would give $1$, not the correct boundary length $2$.

Consequences and a Common Mistake

Corollary: If a finite plane graph has $f$ faces and every face has boundary length $r$, then $rf=2|E|$.

Proof. By assumption, each of the $f$ faces contributes length $r$. Adding these $f$ equal contributions gives total boundary length $rf$. The Theorem says that the same total is $2|E|$. Therefore $rf=2|E|$. $\square$

The theorem also says that the total boundary length is even, because it equals $2|E|$. This does not say that each individual face has even boundary length: in the plane embedding of $K_4$, each of the four faces has length $3$, while the total is $12$.

Common mistake: count each boundary edge only once. In the single-edge example, it is tempting to say that the only face has length $1$, because only one distinct edge appears in the drawing. That count confuses an edge with its boundary occurrences. The face boundary traverses $1$ to $2$ and then $2$ to $1$, so its length is $2$. The correction is to count both sides of every edge, even when they belong to one face.

When applying the formula, first fix the embedding, then count edge traversals around each face with repetitions included. Do not replace a boundary walk by the set of distinct edges it uses. The formula is an incidence count and does not depend on whether the two sides of an edge meet the same face or different faces.

Check Your Understanding

For each question, count boundary traversals with multiplicity, not just distinct edges.

A plane embedding has five edges. What is the total length of all face boundaries?
In a face boundary walk, an edge is traversed twice. How many times does that edge contribute to the boundary length of that face?
In the plane 4-cycle example, verify the total by counting the two sides of each edge rather than by adding face lengths.
A plane graph has four faces, each of boundary length $3$. How many edges does it have?
Explain why the single-edge graph has one face of boundary length $2$, even though its drawing has only one distinct edge.

Edge-Face Incidences and Boundary Length

What You'll Learn