Why Separators Allow Embeddings to Vary
A plane embedding records more than which vertices are adjacent: it also records how the edges are arranged around vertices and which walks bound faces. If a graph can be separated into pieces by deleting one or two vertices, those pieces may sometimes be rearranged while keeping the same graph. This gives concrete examples of why the 3-connectivity hypothesis in Whitney’s unique embedding theorem matters.
All graphs below are finite and simple. A plane embedding represents vertices by distinct points and edges by arcs that meet only at common endpoints. We regard the drawing as lying on the sphere, so there is no distinguished outer face. Two embeddings of the same labelled graph are equivalent if a homeomorphism of the sphere takes each vertex and edge to the corresponding vertex and edge. In particular, equivalent embeddings have the same face-boundary walks, up to changing their starting points or directions. A cut vertex is a vertex whose deletion increases the number of connected components. A 2-vertex separator is a pair of vertices whose deletion disconnects the graph, when the graph is connected and neither vertex alone is a cut vertex.
Whitney’s theorem is a standard result established in the earlier material on unique embeddings. Here the aim is to construct and verify examples showing what can go wrong when the connectivity hypothesis is absent. We will use facial boundary walks as an invariant: a homeomorphism preserving the labelled graph must take each face boundary to a face boundary, preserving its edge sequence up to reversal and cyclic shift.
Reversing a Block at a Cut Vertex
Worked Example: Two Triangles Sharing a Cut Vertex
Let \(G=(V,E)\), where \(V=\{v,a,b,c,d\}\) and \(E=\{va,ab,bv,vc,cd,dv\}\). Thus \(G\) consists of two triangles, \(vabv\) and \(vcdv\), meeting only at \(v\). Deleting \(v\) leaves the two components on \(\{a,b\}\) and \(\{c,d\}\), so \(v\) is a cut vertex.
For the first embedding, draw the two triangles as separate loops meeting at \(v\), with the edge order around \(v\) given by \(va,vb,vc,vd\) in one direction. Its three face-boundary walks are \(v,a,b,v\), \(v,c,d,v\), and \(v,a,b,v,c,d,v\). The last walk bounds the face surrounding both triangles.
Now keep the first triangle fixed and reverse the second triangle around \(v\). The edge order at \(v\) becomes \(va,vb,vd,vc\). This is again a plane embedding: the triangles still meet only at \(v\). The two triangular face boundaries remain, but the remaining face boundary is now \(v,a,b,v,d,c,v\).
Check: The graph has \(5\) vertices and \(6\) edges, so Euler’s formula for a connected plane graph gives \(f=2-|V|+|E|=2-5+6=3\) faces in either embedding, matching the three listed boundaries. The two outer boundary walks differ: neither a cyclic shift nor a reversal of \(v,a,b,v,c,d,v\) gives \(v,a,b,v,d,c,v\). Thus the embeddings are not equivalent when the vertex and edge labels are fixed.
The construction works because the two triangles communicate only through \(v\). Reversing one triangle changes the local arrangement of its incident edges relative to those of the other triangle without changing any adjacency. This is a basic form of embedding nonuniqueness at a cut vertex. The face boundary repeats \(v\), which is expected: a face boundary in a graph with a cut vertex need not be a cycle with distinct vertices.
A Two-Vertex Separator and a Flip
A related rearrangement can occur when two vertices \(u,v\) separate parts of a graph. One useful model consists of several internally vertex-disjoint \(u\)-\(v\) paths. “Internally vertex-disjoint” means that no internal vertex of one path belongs to another path; the paths share only their endpoints \(u,v\). In a plane drawing, the paths occur in a cyclic order around \(u\), and their order around \(v\) is reversed. The regions between consecutive paths are faces.
Proof. Regard the sphere with \(u\) and \(v\) removed as a cylinder. Draw the \(k\) paths as disjoint arcs running from one end of the cylinder to the other. Their labels can be placed in any cyclic order around \(u\); disjointness forces the order at the other end to be the reverse order. The arcs divide the cylinder into \(k\) regions, one between each pair of consecutive arcs. Restoring \(u\) and \(v\), the boundary of each region consists of those two paths, one traversed from \(u\) to \(v\) and the other from \(v\) to \(u\). This constructs the claimed embedding and its face boundaries. \(\square\)
Worked Example: Four Paths with Different Lengths
Let \(G\) have \(V=\{u,v,a,b,c,d,e,f\}\) and \(E=\{uv,ua,av,ub,bc,cv,ud,de,ef,fv\}\). It is the union of four internally vertex-disjoint \(u\)-\(v\) paths: \(P_1=u,v\), \(P_2=u,a,v\), \(P_3=u,b,c,v\), and \(P_4=u,d,e,f,v\). Their lengths are \(1,2,3,4\), respectively. Deleting \(\{u,v\}\) leaves four components, so \(\{u,v\}\) is a 2-vertex separator.
In the first embedding, choose the cyclic order \(P_1,P_2,P_3,P_4\) around \(u\). By the proposition, the four face boundaries use the path pairs \(P_1P_2,P_2P_3,P_3P_4,P_4P_1\). In the second embedding, choose the order \(P_1,P_3,P_2,P_4\). The face boundaries now use \(P_1P_3,P_3P_2,P_2P_4,P_4P_1\). Both embeddings exist by drawing the paths as disjoint arcs on the sphere.
Check: The graph has \(8\) vertices and \(10\) edges, so each connected plane embedding has \(f=2-8+10=4\) faces, as listed. The first embedding has faces using \(P_1P_2\) and \(P_3P_4\), whereas the second has faces using \(P_1P_3\) and \(P_2P_4\). These face-boundary pairs differ. Moreover, the four paths have distinct lengths, so any graph automorphism must preserve each path; swapping \(u\) and \(v\) does not change which pairs of paths bound faces. Thus this difference also rules out equivalence if equivalence is allowed to relabel the graph by an automorphism.
This example is 2-connected: deleting any single vertex leaves the remaining graph connected, since at least one \(u\)-\(v\) path remains and each surviving path segment attaches to an endpoint. But it is not 3-connected: deleting \(u\) and \(v\) leaves four components. It therefore exhibits nonuniqueness that cannot be explained just by the presence of a cut vertex.
What a Separator Does—and Does Not—Guarantee
The examples illustrate a useful principle. A separator identifies where pieces meet; it does not, by itself, guarantee that every rearrangement produces a different embedding. The available choices depend on the structure of the pieces and on whether the resulting facial boundaries actually change.
Worked Example: Three Paths Do Not Give the Same Distinction
Take three internally vertex-disjoint paths \(Q_1,Q_2,Q_3\) between \(u\) and \(v\), with no other vertices or edges. For instance, define \(V=\{u,v,a,b\}\) and \(E=\{uv,ua,av,ub,bv\}\). The paths are \(Q_1=u,v\), \(Q_2=u,a,v\), and \(Q_3=u,b,v\).
Any plane embedding has three faces, each bounded by a pair of paths. Since there are only three pairs, the face-boundary pairs are \(Q_1Q_2,Q_1Q_3,Q_2Q_3\), regardless of the cyclic order. Also, any ordering of three labels around a point can be changed into any other by a cyclic shift or a reversal: there are only three possible starting points in each of the two directions. Thus rearranging these three paths does not produce the distinct facial-boundary pattern seen with four paths.
Check: Here \(|V|=4\) and \(|E|=5\), so Euler’s formula gives \(f=2-4+5=3\), exactly the three path-pair faces. The pair \(Q_1Q_2\) forms the cycle \(u,a,v,u\), \(Q_1Q_3\) forms \(u,b,v,u\), and \(Q_2Q_3\) forms \(u,a,v,b,u\); all three pairs occur.
This comparison prevents an overgeneralization: a 2-vertex separator makes a flip possible to consider, but non-equivalence must still be established. For the four-path graph, changing the cyclic order changes which labelled paths bound faces. For the three-path graph, the set of pairs is unchanged. The relevant test is the embedding information, not merely the existence of a separator.
Why 3-Connectivity Matters
In a 3-connected graph, deleting any one or two vertices leaves the graph connected. There is therefore no cut vertex around which separate blocks can be independently reversed, and no pair whose deletion separates the graph into pieces that can be rearranged in the examples above. Whitney’s theorem says that for planar graphs this stronger connectivity is sufficient for uniqueness of the embedding on the sphere.
Common mistake: “A 2-connected planar graph has a unique embedding.” The four-path graph is a counterexample: it is 2-connected, but the two embeddings have different labelled facial boundaries. The correction is that the hypothesis of Whitney’s theorem is 3-connectivity, not merely 2-connectivity. Another mistake is to infer nonuniqueness just from finding a separator. The three-path example shows why that inference is insufficient: construct candidate embeddings and compare their face boundaries before declaring them inequivalent.
The practical method is to identify the separator, keep track of the labelled pieces attached to it, and record the face boundaries after each proposed rearrangement. A changed face-boundary pattern proves non-equivalence. When the graph is 3-connected, Whitney’s theorem supplies the contrasting conclusion: such a change cannot give a genuinely different embedding of the same graph.
Check Your Understanding
Use face boundaries and the definitions in this tutorial to justify your answers.
- For two triangles sharing one vertex, which face boundary changes when one triangle is reversed at the shared vertex?
- In the four-path example, list the path pairs bounding faces in the embedding with cyclic order \(P_1,P_3,P_2,P_4\).
- Why does deleting the two endpoints of the four-path graph disconnect it, while deleting only one vertex does not?
- Explain why different cyclic orders of three paths need not produce different face-boundary pairs.
- State the connectivity hypothesis in Whitney’s unique embedding theorem and identify which examples here fail it.