Peripheral Cycles and Their Characterization

Peripheral Cycles: A Graph-Theoretic Description of Faces

A face is part of a particular drawing of a planar graph, while a cycle is specified by vertices and edges. In a three-connected planar graph, a cycle has a particularly useful description that does not refer to a drawing: it is a facial cycle exactly when it is induced and deleting its vertices leaves a connected graph. This lets us recognize the facial cycles from the abstract graph and then, in a plane embedding, identify the regions they bound.

All graphs in this tutorial are finite and simple. A plane graph is a graph together with a fixed embedding in the plane, with edges meeting only at common endpoints. A planar graph is one that has such an embedding. A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated initial and final vertex, are distinct. A cycle is induced if no two of its nonconsecutive vertices are adjacent; in other words, the subgraph induced by its vertices has exactly the cycle edges.

A graph is three-connected if it has at least four vertices and deleting any set of fewer than three vertices leaves a connected graph. We use the established fact that in a three-connected plane graph every face boundary is a cycle. The characterization below concerns a fixed plane embedding, but its peripheral condition depends only on the abstract graph.

Jordan Separation for Three Attachments

The key separation fact is about a disk whose boundary contains a cycle. Suppose a connected subgraph lies inside the disk and meets its boundary at three distinct vertices. That subgraph separates the disk into regions. Any other connected subgraph drawn inside the disk, disjoint from the first except that both may attach to the boundary, must be confined to one of those regions.

Proof. Inside \(A\), take a minimal tree joining its attachment points \(x,y,z\), together with the edges from that tree to the three boundary vertices. Suppressing vertices of degree two in this tree gives a tree with three leaves \(x,y,z\) and one branch point. The tree is drawn inside \(D\) and meets the boundary only at those leaves. By the Jordan curve theorem, this tree divides the disk into three regions: the boundary of each region includes one of the open arcs between consecutive points of \(x,y,z\), together with the tree paths bounding that region. Since \(B\) is connected and disjoint from the tree in the interior of \(D\), its drawing lies in one region. Its attachment points must therefore lie on the closure of that region, hence in the corresponding closed boundary arc. Each such arc contains only two of \(x,y,z\), so \(B\) cannot attach at all three. \(\square\)

Characterization of Facial Cycles

Proof. First suppose \(C\) is facial. Its drawing is a simple closed curve, and the graph apart from \(C\) lies on the side opposite the face bounded by \(C\).

We first show that \(C\) is induced. Suppose there were a chord \(uv\), an edge joining two nonconsecutive vertices of \(C\). The chord lies on the side opposite the face and, together with either of the two \(u\)-to-\(v\) arcs of \(C\), separates the disk on that side. Since \(u,v\) are nonconsecutive, each arc has an internal vertex. After deleting \(u\) and \(v\), the internal vertices of the two arcs lie on opposite sides of the chord, and no path can join them without crossing the chord or passing through \(u\) or \(v\). Thus \(G-\{u,v\}\) is disconnected, contradicting three-connectivity. So \(C\) has no chord and is induced.

We next show that \(G-V(C)\) is connected. For a component \(K\) of \(G-V(C)\), call a vertex of \(C\) an attachment of \(K\) if it is adjacent to a vertex of \(K\), and let \(S_K\) be the set of attachments of \(K\). All neighbors of vertices of \(K\) lie in \(K\) or in \(S_K\). Since \(C\) is facial, every component lies in the closed disk \(D\) bounded by \(C\) on the side opposite the face.

Step 1: \(G-V(C)\) is nonempty. Otherwise \(V(G)=V(C)\), and since \(C\) is induced, \(G\) is the cycle \(C\). A cycle on three vertices has fewer than four vertices, so it is not three-connected. In a longer cycle, deleting two nonconsecutive vertices leaves a disconnected graph. Either way three-connectivity fails.

Step 2: every component has at least three attachments. Let \(K\) be a component. If \(|S_K|\le2\), delete \(S_K\). Since \(C\) has at least three vertices, some vertex of \(C\) survives, and \(K\) is separated from it, because every neighbor of \(K\) outside \(K\) was deleted. This contradicts three-connectivity.

Step 3: there are not two components. Suppose \(A\) and \(B\) are distinct components. First we show that there are points \(p,q\in S_A\) such that \(S_B\subseteq[p,q]\), where \([p,q]\) is a closed arc of \(C\), and no point of \(S_A\) lies strictly between \(p\) and \(q\) on that arc.

By Step 2, \(|S_A|\ge3\) and \(|S_B|\ge3\). Take any three points \(x,y,z\in S_A\). By the lemma, \(S_B\) lies in one of the three closed arcs between consecutive points of \(x,y,z\). Such an arc has two of the three points as endpoints and does not contain the third. So there are pairs \((p,q)\) of points of \(S_A\) with \(S_B\subseteq[p,q]\) and some point of \(S_A\) outside \([p,q]\). Among these pairs, choose one for which the open arc \((p,q)\) contains as few points of \(S_A\) as possible. Suppose some \(t\in S_A\) lies in \((p,q)\), and let \(z\in S_A\) lie outside \([p,q]\). Apply the lemma to \(p,t,z\): the set \(S_B\), which lies in \([p,q]\), must lie in one of the closed arcs \([p,t]\), \([t,z]\), \([z,p]\). Within \([p,q]\) these give \([p,t]\), \([t,q]\), and the single point \(p\). Since \(|S_B|\ge3\), either \(S_B\subseteq[p,t]\) or \(S_B\subseteq[t,q]\). In either case a pair with fewer points of \(S_A\) strictly inside would exist, which contradicts the choice. Hence no point of \(S_A\) lies strictly between \(p\) and \(q\).

Let \(I\) be the set of vertices of \(C\) strictly between \(p\) and \(q\). Since \(S_B\subseteq[p,q]\) has at least three points and only \(p,q\) are endpoints, some attachment of \(B\) lies in \(I\). Let \(Y\) consist of the vertices in \(I\) together with all vertices of every component \(K\) with \(S_K\cap I\neq\varnothing\). Then \(Y\) is nonempty, as \(B\subseteq Y\).

Every such component \(K\) satisfies \(S_K\subseteq[p,q]\). This is clear for \(K=B\). Also \(K\neq A\), since \(S_A\cap I=\varnothing\). For other \(K\), the argument just given with \(K\) in place of \(B\) shows that \(S_K\) lies in a closed arc \([p',q']\) between points of \(S_A\) with none of \(S_A\) strictly between. Because \(S_K\) has a point in \(I\), which contains no point of \(S_A\), that arc must be \([p,q]\).

Now delete \(p\) and \(q\). A vertex of \(I\) has neighbors on \(C\) only in \(I\cup\{p,q\}\), because \(C\) is induced, so it has no chords. Its neighbors off \(C\) lie in components \(K\) with \(S_K\cap I\neq\varnothing\), which belong to \(Y\). A vertex of such a component \(K\) has neighbors only in \(K\) or in \(S_K\subseteq I\cup\{p,q\}\). So no edge joins \(Y\) to a vertex outside \(Y\cup\{p,q\}\). That outside set is nonempty: it contains \(A\), since \(A\) has no attachment in \(I\) and so is not in \(Y\). Therefore \(G-\{p,q\}\) is disconnected, contradicting three-connectivity.

Hence \(G-V(C)\) is nonempty and has exactly one component. It is connected, and \(C\) is peripheral.

Conversely, suppose \(C\) is peripheral. Its drawing is a simple closed curve, so the Jordan curve theorem divides the plane into two sides. The connected graph \(G-V(C)\) is nonempty and lies entirely on one side: a path in that graph cannot cross \(C\), because edges of a plane graph do not cross. On the other side there are no vertices of \(G-V(C)\). There are also no edges joining nonconsecutive vertices of \(C\), because \(C\) is induced. Therefore that side contains no part of the graph in its interior, and it is a face bounded by \(C\). Hence \(C\) is facial. \(\square\)

Worked Examples

Using the Characterization Carefully

The two conditions in “peripheral” have different jobs. Inducedness rules out chords that could divide the side of the cycle into separate regions. Connectivity of \(G-V(C)\), together with Jordan separation, ensures that all vertices away from the cycle lie on one side, leaving the other side empty and therefore a face.

A common mistake is to use only one condition. In \(K_4\), the 4-cycle \(1,2,4,3,1\) uses all four vertices, so deleting it leaves the empty graph, which is not connected under our convention. It also has the chords \(14\) and \(23\). Conversely, a cycle can be induced while its deletion leaves several components, and then it is not facial. The equatorial 4-cycle of the octahedron is an example. Its two poles are each joined to all four equatorial vertices, and opposite equatorial vertices are not adjacent, so the cycle is induced. But deleting it leaves the two poles, which are not adjacent to each other. The octahedron is three-connected and planar, and every face is a triangle, so this cycle bounds no face. Check both conditions, and use the theorem only when the graph is three-connected and planar.

The topological separation step also needs care. It is not enough to compare two components using three of their attachments. A component \(A\) may have many more attachments, and some of them can lie in the arc where \(B\) attaches. The proof therefore chooses points \(p,q\) of \(S_A\) with no attachment of \(A\) strictly between them, and then deletes exactly \(p\) and \(q\). This separates everything attached strictly between them from the rest of the graph, including \(A\).

Peripheral cycles are useful because they convert a property of a drawing into a property of the graph itself. In a three-connected planar graph, once the cycles satisfying the two graph-theoretic conditions are found, the theorem says exactly which cycles bound faces in any chosen plane embedding.