From Peripheral Cycles to Unique Embeddings
A planar graph can have many drawings, even on the sphere: vertices may be moved and edges may be bent without changing the embedding’s essential structure. Whitney’s theorem says that for a 3-connected planar graph, this flexibility does not produce genuinely different embeddings. The key is to recover the faces from the abstract graph alone. In this setting, a cycle is facial exactly when it is peripheral: it has no chord, and deleting its vertices leaves a connected graph. Thus every spherical embedding has the same facial cycles, and those cycles determine how the faces fit together.
Throughout, graphs are finite and simple. An embedding on the sphere places distinct vertices at distinct points and represents each edge by an arc joining its endpoints, with edge interiors disjoint from one another and from all vertices. A face is a connected region of the sphere outside the embedded graph. A graph is 3-connected if it has at least four vertices and deleting any set of at most two vertices leaves a connected graph. A cycle is induced if no two of its nonconsecutive vertices are joined by an edge.
The “at most one” formulation includes the empty remainder. For a 3-connected graph of order at least four, a peripheral cycle cannot use every vertex: if it did, it would be a spanning induced cycle, and any additional edge would be a chord, while the cycle itself would not meet the usual peripheral condition if the empty remainder is excluded. We will use the standard formulation with connected remainder for cycles that arise below; in particular, the examples have nonempty remainders. More generally, the facial-cycle characterization for a 3-connected plane graph uses the conventional peripheral condition that deleting the cycle leaves a connected graph or the empty graph.
We use the following standard characterization, established in the earlier material on peripheral cycles: in a 3-connected plane graph, a cycle is facial if and only if it is peripheral. A facial cycle is the boundary of one face. The characterization applies separately to every embedding of the same 3-connected planar graph. We will use it to identify the face boundaries without choosing a drawing.
Why Facial-Cycle Data Determines an Embedding
The face boundaries are more than a list of cycles. In a 3-connected plane graph, each face is a disk bounded by a cycle, each edge has one face on each side, and no two distinct faces have the same boundary cycle. These are standard properties of 2-connected plane graphs and their facial cycles. Consequently, the collection of facial cycles tells us which face boundaries meet along each edge.
Proof. For each facial cycle, take a closed disk whose boundary is marked by the vertices and edges of that cycle, in their cyclic order. Do this once for each facial cycle. For every edge \(uv\), exactly two facial cycles contain \(uv\), one for each side of the edge in the embedding. Identify the two copies of the edge \(uv\), matching \(u\) to \(u\) and \(v\) to \(v\). The resulting surface is the sphere with the embedded graph as its one-dimensional skeleton and the face disks as its two-dimensional regions.
Because the facial cycles are the same in the two embeddings, the same disks, boundary vertices, boundary edges and edge identifications can be used for both. Map each marked disk boundary to the corresponding boundary in the other embedding, edge by edge and vertex by vertex. This boundary map extends over the disk: a homeomorphism of a circle extends to its disk, for example by mapping each radius to the corresponding radius. The disk maps agree on identified edges, so together they give a homeomorphism of the assembled spheres that maps the graph of the first embedding to the graph of the second, preserving each vertex and edge. A homeomorphism of the sphere is either orientation preserving or orientation reversing, so the equivalence allows reflection. \(\square\)
The construction explains why the full face-boundary data matters: an edge is glued to the face on its other side, and the cycles specify which face that is. No independent choice of how to arrange the faces remains.
Whitney’s Unique Embedding Theorem
Proof. Let \(G\) be a 3-connected planar graph, and choose any two embeddings of \(G\) on the sphere. A cycle is peripheral if and only if it is induced and deleting its vertices leaves a connected graph (or, under the equivalent convention, the empty graph). Both conditions are properties of the abstract graph: neither depends on an embedding. Thus the two embeddings have exactly the same peripheral cycles.
By the peripheral-cycle characterization, in each embedding the facial cycles are exactly the peripheral cycles. Therefore the two embeddings have the same collection of facial cycles. The reconstruction principle now gives a homeomorphism of the sphere carrying one embedded graph to the other. If that homeomorphism reverses orientation, it is a reflection in the allowed sense. Hence the embedding is unique up to homeomorphism and reflection. \(\square\)
Worked Examples
Worked Example: The Complete Graph \(K_4\)
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). The graph is 3-connected: after deleting any two vertices, the two remaining vertices are joined by their edge; after deleting at most one vertex, the remaining complete graph is connected.
Every three vertices induce a triangle, since every pair is an edge. Deleting the vertices of any such triangle leaves one vertex, which has one connected component. Hence all four triangles are peripheral. Independently, there are exactly \(\binom{4}{3}=4\) three-vertex subsets, so this list accounts for every triangle. The peripheral-cycle characterization says that these four triangles are precisely the face boundaries in every spherical embedding.
Check: The count of four facial cycles is consistent with Euler’s formula for a connected plane graph, \(n-m+f=2\): here \(n=4\), \(m=6\), so \(f=2-4+6=4\). Whitney’s theorem then says that any two embeddings have the same four face boundaries and are equivalent up to homeomorphism and reflection.
Worked Example: A Wheel with a Four-Vertex Rim
Let \(G\) have \(V=\{h,1,2,3,4\}\) and \(E=\{12,23,34,41,h1,h2,h3,h4\}\). This is the wheel with hub \(h\) and rim \(1,2,3,4,1\). It is 3-connected. If \(h\) remains after at most two vertices are deleted, every remaining rim vertex is adjacent to \(h\), so the remaining graph is connected. If \(h\) is deleted, at most one rim vertex is also deleted; the remaining rim is either a 4-cycle or a path on three vertices, each connected.
The rim cycle \(1,2,3,4,1\) is induced: its only possible chords are \(13\) and \(24\), neither of which is an edge. Deleting its vertices leaves \(\{h\}\), which has one connected component, so the rim is peripheral. Each of the four triangles \(h12h\), \(h23h\), \(h34h\) and \(h41h\) is also peripheral. For instance, \(h12h\) is induced because \(h1,h2,12\) are its three edges, and deleting \(\{h,1,2\}\) leaves the edge \(34\), a connected graph. The same check applies to each successive rim edge.
Thus the four triangles and the rim cycle are facial in every embedding. The list contains five distinct cycles. As a count check, this graph has \(n=5\) vertices and \(m=8\) edges, so Euler’s formula gives \(f=2-5+8=5\). The five identified facial cycles account for all faces, and the embedding is unique up to homeomorphism and reflection.
Worked Example: The Triangular Prism
Let \(V=\{a_1,a_2,a_3,b_1,b_2,b_3\}\), with edges \(a_1a_2,a_2a_3,a_3a_1\), \(b_1b_2,b_2b_3,b_3b_1\), and \(a_1b_1,a_2b_2,a_3b_3\). This graph consists of two triangles joined by three corresponding edges.
It is 3-connected. If at most two deleted vertices lie in one triangle, the other triangle remains intact, and every surviving vertex in the damaged triangle is joined by a corresponding edge to that intact triangle. If one vertex is deleted from each triangle, the two remaining vertices in each triangle are adjacent; at least one index \(i\) remains in both layers, so \(a_ib_i\) joins the two remaining pairs. With no deletions, or one deletion, connectivity also follows directly from the two triangles and their corresponding edges.
The top triangle \(a_1a_2a_3a_1\) and the bottom triangle \(b_1b_2b_3b_1\) are induced. Deleting the top triangle leaves the connected bottom triangle, and deleting the bottom triangle leaves the connected top triangle. The three side cycles, for example \(a_1a_2b_2b_1a_1\), are induced: the two possible cross-edges \(a_1b_2\) and \(a_2b_1\) are absent, and the other edges between its vertices are already on the cycle. Deleting the vertices of this side cycle leaves \(a_3,b_3\) and the edge \(a_3b_3\), so the remainder is connected. The same calculation applies to the other two side cycles.
These five cycles are therefore facial in every embedding. As an independent count, the graph has \(n=6\) vertices and \(m=9\) edges, and Euler’s formula gives \(f=2-6+9=5\). Thus the two triangular and three quadrilateral cycles account for all faces. The theorem guarantees that every spherical embedding has this same face data and is equivalent to every other one.
Scope and a Common Pitfall
The proof depends on 3-connectivity in two places: it gives the peripheral-cycle characterization, and it rules out the small separators that can allow different pieces of an embedding to be rearranged. The theorem is a statement about embeddings on the sphere; it does not say that every drawing looks identical, only that the drawings are related by a homeomorphism, possibly orientation reversing.
Common mistake: counting the empty graph as disconnected in the wrong condition. If a cycle in \(K_4\) uses three vertices, deleting those vertices leaves one vertex, and that remainder has one connected component, not zero. The triangle is still peripheral. If instead a cycle uses all vertices, deleting it leaves the empty graph, which has zero connected components; whether that case is admitted is why the peripheral-cycle convention must be stated precisely. In the 3-connected examples above, each listed cycle has a nonempty connected remainder, so no empty-remainder convention is needed for those checks.
A second caution is that a list of cycles determines the embedding here because every facial boundary is a cycle and each edge lies on the boundaries of exactly two faces. Without those hypotheses, repeated face boundaries or noncyclic face boundaries can make reconstruction more delicate. Whitney’s theorem applies to 3-connected planar graphs, not to arbitrary planar graphs.
Check Your Understanding
Use the definitions and reconstruction argument to answer the following questions.
- In the \(K_4\) example, how many connected components remain after deleting the vertices of a triangle, and why does that make the triangle peripheral?
- For the wheel example, verify that the rim cycle has no chord and state the graph left after deleting its vertices.
- Explain why two embeddings with the same facial cycles identify the two copies of each edge in the same way.
- Why does the proof compare peripheral cycles as properties of the abstract graph before using the reconstruction principle?
- State one role that 3-connectivity plays in Whitney’s theorem.