Facial Cycles in Three-Connected Plane Graphs

Faces and Three-Connectivity

In a plane graph, the boundary of a face is traced by following the edges and vertices encountered as one travels around that face. In general, this boundary is a closed walk, and vertices may occur more than once. Three-connectivity rules out that repetition: each face boundary is a cycle. It also imposes a stronger condition on that cycle: removing all its vertices does not split the rest of the graph into separate pieces.

All graphs below are finite and simple. A plane graph is a graph together with a fixed embedding in the plane in which edges meet only at common endpoints. Its faces are the regions of the plane left after drawing the graph, including the unbounded region. A facial boundary walk is the closed walk obtained by tracing one side of the edges around a face; its length counts edge traversals, including repeated traversals. A cycle is a closed walk of length at least three whose vertices, apart from the repeated starting and ending vertex, are distinct.

In particular, a 3-connected graph is connected and has no cut vertex: deleting any single vertex leaves a connected graph. Its minimum degree is at least three. Indeed, if a vertex had at most two neighbors, deleting all its neighbors would leave it isolated while at least one other vertex remained, contrary to 3-connectivity.

Why a Facial Boundary Cannot Repeat a Vertex

Proof. The single-edge exception has a repeated traversal on its only face, so consider a connected plane graph with no cut vertex that is not a single edge. Suppose a face boundary visits a vertex \(v\) more than once. Around \(v\), the incident edges occur in a cyclic order, and each visit to \(v\) on the facial boundary uses a sector between consecutive incident edges. Two different visits to the same face therefore give two distinct sectors belonging to that face. On each of the two portions of the cyclic order between these sectors there is at least one incident edge; otherwise the sectors would be the same sector.

Choose an incident edge \(vx\) from one portion and an incident edge \(vy\) from the other. Since the graph has no cut vertex, there is an \(x\)-to-\(y\) path avoiding \(v\). Choose such a path with no repeated vertices. Together with \(vx\) and \(vy\), it forms a cycle. Near \(v\), the cycle separates the two selected sectors: they lie on opposite sides of the cycle. By the Jordan curve theorem, a face cannot meet both sides of a drawn cycle without crossing it. This contradicts the assumption that both sectors belong to the same face. Thus no facial boundary repeats a vertex. In a simple graph, a closed boundary walk without repeated vertices is a cycle; the graph cannot have a facial boundary of length one or two here, since it has no loops, multiple edges, or bridges. A 3-connected graph has no cut vertex and is not a single edge, so the conclusion applies. \(\square\)

The lemma addresses only the shape of the boundary. It does not yet say what remains when the boundary vertices are deleted. That second claim uses the way connected subgraphs can sit inside the disk bounded by a facial cycle.

Removing a Facial Cycle Leaves a Connected Graph

Here a component's neighbors on \(C\) are the vertices of \(C\) joined by an edge to some vertex of that component. To see the separation fact, draw the graph in the disk on the side of \(C\) opposite the face. For \(H\), take a minimal connected subgraph joining all its neighbors on \(C\), together with one edge to \(H\) for each such neighbor. This subgraph can be taken to be a tree. Its branches divide the disk into regions whose boundary arcs on \(C\) run between consecutive neighbors of \(H\). The connected component \(K\), being disjoint from \(H\), lies in one such region. Its neighbors on \(C\) must lie on that region's boundary arc, including the two endpoints. Since \(K\) has at least three distinct neighbors, at least one lies strictly between the endpoints.

The arc and the tree path between its endpoints form a closed curve. The Jordan curve theorem says this curve separates the region containing \(K\) from the rest of the disk. No other component can cross the curve, and the arc has no neighbor of \(H\) in its interior because its endpoints were consecutive neighbors of \(H\). Deleting the two endpoints therefore separates the vertices in the region containing \(K\) from the rest. The region still contains a vertex of \(K\), since \(K\) has a neighbor strictly inside the arc. This proves the stated fact.

Proof. By the lemma, the boundary of the chosen face is a cycle \(C\). Suppose \(G-V(C)\) has at least two components. Let \(H\) be any one of them, and let \(A\) be the set of its neighbors on \(C\). If \(|A|\leq 2\), delete \(A\). The vertices of \(H\) remain, and they have no edges to any other component of \(G-V(C)\); all their neighbors on \(C\) have been deleted. At least one vertex of \(C\) remains, since a cycle has at least three vertices. Thus the deletion disconnects the graph, contradicting 3-connectivity. Hence every component of \(G-V(C)\) has at least three distinct neighbors on \(C\).

Apply the planar separation fact to two of the components. It gives two vertices of \(C\) whose deletion disconnects \(G\), again contradicting 3-connectivity. Therefore \(G-V(C)\) has at most one component, which proves it is connected or empty.

For completeness, the empty case is impossible here. If every vertex of \(G\) lay on \(C\), the graph would consist of \(C\) and noncrossing chords drawn on the side opposite the face. If there were no chord, every vertex would have degree two, contrary to minimum degree at least three. If there were a chord \(xy\), the two arcs of \(C\) between \(x\) and \(y\) would each contain an internal vertex. Deleting \(x\) and \(y\) separates those two sets of internal vertices: an edge joining the sets would cross the chord or the boundary of the face. This contradicts 3-connectivity. Thus some vertex lies outside \(C\), and \(G-V(C)\) is nonempty and connected. \(\square\)

Worked Examples

Common Pitfall

Do not equate “no edges” with “disconnected.” In the tetrahedral example, deleting the three vertices of the face \(abc\) leaves one vertex and no edges. A mistaken count might say “zero edges, so disconnected.” Connectedness requires a path between every pair of distinct vertices; a one-vertex graph has no such pair and is connected. The number of edges alone does not decide connectedness.

Another tempting but invalid shortcut is to say that \(G-V(C)\) is connected because \(G\) is 3-connected. The definition only guarantees connectedness after deleting at most two vertices, whereas a face boundary can have more than two vertices. The theorem needs the plane embedding: if the deletion left multiple components, each would have at least three attachments to the cycle, and planar separation would force a forbidden pair of vertices whose deletion disconnects \(G\).