In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, 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, the 3-connected planar graphs are also known as polyhedral graphs.
This result provides a classification theorem for the three-dimensional convex polyhedra, something that is not known in higher dimensions. It provides a complete and purely combinatorial description of the vertex-edge graphs of these polyhedra, allowing other results on them, such as Eberhard's theorem on the realization of polyhedra with given types of faces, to be proven more easily, without reference to the geometry of these shapes. Additionally, it has been applied in graph drawing, as a way to construct three-dimensional visualizations of abstract graphs. Branko Grünbaum has called this theorem "the most important and deepest known result on 3-polytopes."
The theorem appears in a 1922 publication of Ernst Steinitz, after whom it is named. It can be proven by mathematical induction (as Steinitz did), by finding the minimum-energy state of a two-dimensional spring system and lifting the result into three dimensions, or by using the circle packing theorem. Several extensions of the theorem are known, in which the polyhedron that realizes a given graph has additional constraints; for instance, every polyhedral graph is the graph of a convex polyhedron with integer coordinates, or the graph of a convex polyhedron all of whose edges are tangent to a common midsphere.
Definitions and statement of the theorem
An undirected graph is a system of vertices and edges, each edge connecting two of the vertices. As is common in graph theory, for the purposes of Steinitz's theorem these graphs are restricted to being finite (the vertices and edges are finite sets) and simple (no two edges connect the same two vertices, and no edge connects a vertex to itself). From any polyhedron one can form a graph, by letting the vertices of the graph correspond to the vertices of the polyhedron and by connecting any two graph vertices by an edge whenever the corresponding two polyhedron vertices are the endpoints of an edge of the polyhedron. This graph is known as the skeleton of the polyhedron.More technically, this graph is the 1-skeleton; see , p. 138, and , p. 64.
A graph is planar if it can be drawn with its vertices as points in the Euclidean plane, and its edges as curves that connect these points, such that no two edge curves cross each other and such that the point representing a vertex lies on the curve representing an edge only when the vertex is an endpoint of the edge. By Fáry's theorem, every planar drawing can be straightened so that the curves representing the edges are line segments. A graph is 3-connected if it has more than three vertices and, after the removal of any two of its vertices, any other pair of vertices remain connected by a path. Steinitz's theorem states that these two conditions are both necessary and sufficient to characterize the skeletons of three-dimensional convex polyhedra: a given graph is the graph of a convex three-dimensional polyhedron, if and only if is planar and 3-vertex-connected.
Proofs
One direction of Steinitz's theorem (the easier direction to prove) states that the graph of every convex polyhedron is planar and 3-connected. As shown in the illustration, planarity can be shown by using a Schlegel diagram: if one places a light source near one face of the polyhedron, and a plane on the other side, the shadows of the polyhedron edges will form a planar graph, embedded in such a way that the edges are straight line segments. The 3-connectivity of a polyhedral graph is a special case of Balinski's theorem that the graph of any -dimensional convex polytope is -connected. The connectivity of the graph of a polytope, after removing any of its vertices, can be proven by choosing one more vertex , finding a linear function that is zero on the resulting set of vertices, and following the paths generated by the simplex method to connect every vertex to one of two extreme vertices of the linear function, with the chosen vertex connected to both.
The other, more difficult, direction of Steinitz's theorem states that every planar 3-connected graph is the graph of a convex polyhedron. There are three standard approaches for this part: proofs by induction, lifting two-dimensional Tutte embeddings into three dimensions using the Maxwell–Cremona correspondence, and methods using the circle packing theorem to generate a canonical polyhedron.
Induction
Although Steinitz's original proof was not expressed in terms of graph theory, it can be rewritten in those terms, and involves finding a sequence of ΔY- and YΔ-transformations that reduce any 3-connected planar graph to , the graph of the tetrahedron. A YΔ-transformation removes a degree-three vertex from a graph, adding edges between all of its former neighbors if those edges did not already exist; the reverse transformation, a ΔY-transformation, removes the edges of a triangle from a graph and replaces them by a new degree-three vertex adjacent to the same three vertices. Once such a sequence is found, it can be reversed and converted into geometric operations that build up the desired polyhedron step by step starting from a tetrahedron. Each YΔ-transformation in the reversed sequence can be performed geometrically by slicing off a degree-three vertex from a polyhedron. A ΔY-transformation in the reversed sequence can be performed geometrically by removing a triangular face from a polyhedron and extending its neighboring faces until the point where they meet, but only when that triple intersection point of the three neighboring faces is on the far side of the removed face from the polyhedron. When the triple intersection point is not on the far side of this face, a projective transformation of the polyhedron suffices to move it to the correct side. Therefore, by induction on the number of ΔY- and YΔ-transformations needed to reduce a given graph to , every polyhedral graph can be realized as a polyhedron.
A later work by Epifanov strengthened Steinitz's proof that every polyhedral graph can be reduced to by ΔY- and YΔ-transformations. Epifanov proved that if two vertices are specified in a planar graph, then the graph can be reduced to a single edge between those terminals by combining ΔY- and YΔ-transformations with series–parallel reductions. Epifanov's proof was complicated and non-constructive, but it was simplified by Truemper using methods based on graph minors. Truemper observed that every grid graph is reducible by ΔY- and YΔ-transformations in this way, that this reducibility is preserved by graph minors, and that every planar graph is a minor of a grid graph. This idea can be used to replace Steinitz's lemma that a reduction sequence exists. After this replacement, the rest of the proof can be carried out using induction in the same way as Steinitz's original proof. For these proofs, carried out using any of the ways of finding sequences of ΔY- and YΔ-transformations, there exist polyhedral graphs that require a nonlinear number of steps. More precisely, every planar graph can be reduced using a number of steps at most proportional to , and infinitely many graphs require a number of steps at least proportional to , where is the number of vertices in the graph.
An alternative form of induction proof is based on removing edges (and compressing out the degree-two vertices that might be left after this removal) or contracting edges and forming a minor of the given planar graph. Any polyhedral graph can be reduced to by a linear number of these operations, and again the operations can be reversed and the reversed operations performed geometrically, giving a polyhedral realization of the graph. However, while it is simpler to prove that a reduction sequence exists for this type of argument, and the reduction sequences are shorter, the geometric steps needed to reverse the sequence are more complicated.
Lifting
If a graph is drawn in the plane with straight line edges, then an equilibrium stress is defined as an assignment of nonzero real numbers (weights) to the edges, with the property that each vertex is in the position given by the weighted average of its neighbors. According to the Maxwell–Cremona correspondence, an equilibrium stress can be lifted to a piecewise linear continuous three-dimensional surface such that the edges forming the boundaries between the flat parts of the surface project to the given drawing. The weight and length of each edge determines the difference in slopes of the surface on either side of the edge, and the condition that each vertex is in equilibrium with its neighbors is equivalent to the condition that these slope differences cause the surface to meet up with itself correctly in the neighborhood of the vertex. Positive weights translate to convex dihedral angles between two faces of the piecewise linear surface, and negative weights translate to concave dihedral angles. Conversely, every continuous piecewise-linear surface comes from an equilibrium stress in this way. If a finite planar graph is drawn and given an equilibrium stress in such a way that all interior edges of the drawing have positive weights, and all exterior edges have negative weights, then by translating this stress into a three-dimensional surface in this way, and then replacing the flat surface representing the exterior of the graph by its complement in the same plane, one obtains a convex polyhedron, with the additional property that its perpendicular projection onto the plane has no crossings.
The Maxwell–Cremona correspondence has been used to obtain polyhedral realizations of polyhedral graphs by combining it with a planar graph drawing method of W. T. Tutte, the Tutte embedding. Tutte's method begins by fixing one face of a polyhedral graph into convex position in the plane. This face will become the outer face of a drawing of a graph. The method continues by setting up a system of linear equations in the vertex coordinates, according to which each remaining vertex should be placed at the average of its neighbors. Then as Tutte showed, this system of equations will have a unique solution in which each face of the graph is drawn as a convex polygon. Intuitively, this solution describes the pattern that would be obtained by replacing the interior edges of the graph by ideal springs and letting them settle to their minimum-energy state. The result is almost an equilibrium stress: if one assigns weight one to each interior edge, then each interior vertex of the drawing is in equilibrium. However, it is not always possible to assign negative numbers to the exterior edges so that they, too, are in equilibrium. Such an assignment is always possible when the outer face is a triangle, and so this method can be used to realize any polyhedral graph that has a triangular face. If a polyhedral graph does not contain a triangular face, its dual graph does contain a triangle and is also polyhedral, so one can realize the dual in this way and then realize the original graph as the polar polyhedron of the dual realization. An alternative method for realizing polyhedra using liftings avoids duality by choosing any face with at most five vertices as the outer face. Every polyhedral graph has such a face, and by choosing the fixed shape of this face more carefully, the Tutte embedding of the rest of the graph can be lifted.
Circle packing