Connectedness and polyhedrality

An abstract graph is said to be n-connected if, after the removal of any n-1 of its vertices, all of the remaining vertices are still connected. Connectedness is a property inherited by any map that is an embedding of the abstract graph.

Steinitz's theorem establishes that every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, planar 3-connected graphs are also called polyhedral graphs; their maps (their proper embeddings) are called polyhedral maps.

Since any map that is described by an undip word has a cycle containing all of the vertices (i.e., the hamiltonian cycle the word encodes,) removing a single vertex will open the cycle but not disconnect it. To disconnect the cycle we must remove a pair of vertices that are non-adjacent in the cycle. Therefore: all undip-coded maps are at least 2-connected.

We may also see that disconnecting a trivalent map by the removal of three vertices is unremarkable: removing the three neighbors of any given vertex will always suffice for this. Therefore: no undip-coded maps are more than 3-connected.

The case we need to detect is 2-connectedness. For an undip-coded map to be only 2-connected, the removal of some certain pair of vertices non-adjacent in the hamiltonian cycle (such being necessary and sufficient to disconnect the hamiltonian cycle) must suffice to completely disconnect the map. Therefore, all paths between the two (to-be-separated) portions of the hamiltonian cycle must pass through the two (to-be-deleted) vertices.