# Steinitz's theorem

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.[1] This result provides a classification theorem for the three-dimensional convex polyhedra, something that is not known in higher dimensions.[2] It provides a complete and purely combinatorial description of the 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.[3] Additionally, it has been applied in graph drawing, as a way to construct three-dimensional visualizations of abstract graphs.[4] Branko Grünbaum has called this theorem "the most important and deepest known result on 3-polytopes."[5] The theorem appears in a 1922 publication of Ernst Steinitz,[6] 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.

Contents 1 Definitions and statement of the theorem 2 Proofs 2.1 Induction 2.2 Lifting 2.3 Circle packing 3 Realizations with additional properties 3.1 Integer coordinates 3.2 Equal slopes 3.3 Specifying the shape of a face 3.4 Tangent spheres 4 Related results 5 History 6 References Definitions and statement of the theorem Illuminating the skeleton of a convex polyhedron from a light source close to one of its faces causes its shadows to form a planar Schlegel diagram.

An undirected graph is a system of vertices and edges, each edge connecting two of the vertices. 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.[7] 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 {displaystyle G} is the graph of a convex three-dimensional polyhedron, if and only if {displaystyle G} is planar and 3-vertex-connected.[5][8] Proofs Illustration of the proof of Balinski's theorem, showing the zero set of a linear function (blue) passing through two given vertices (yellow) and the simplex-method paths connecting the remaining graph (green) 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 {displaystyle k} -dimensional convex polytope is {displaystyle k} -connected. The connectivity of the graph of a polytope, after removing any {displaystyle k-1} of its vertices, can be proven by choosing one more vertex {displaystyle v} , finding a linear function that is zero on the resulting set of {displaystyle k} 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 {displaystyle v} connected to both.[9] 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 Δ-Y and Y-Δ transforms of a polyhedron 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-Δ transforms that reduce any 3-connected planar graph to {displaystyle K_{4}} , the graph of the tetrahedron. A Y-Δ transform 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 transform, 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-Δ transform in the reversed sequence can be performed geometrically by slicing off a degree-three vertex from a polyhedron. A Δ-Y transform 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-Δ transforms needed to reduce a given graph to {displaystyle K_{4}} , every polyhedral graph can be realized as a polyhedron.[5] A later work by Epifanov strengthened Steinitz's proof that every polyhedral graph can be reduced to {displaystyle K_{4}} by Δ-Y and Y-Δ transforms. 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-Δ transforms with series–parallel reductions.[10] 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-Δ transforms in this way, that this reducibility is preserved by graph minors, and that every planar graph is a minor of a grid graph.[11] 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.[8] For these proofs, carried out using any of the ways of finding sequences of Δ-Y and Y-Δ transforms, there exist polyhedral graphs that require a nonlinear number of steps. More precisely, infinitely many graphs require a number of steps at least proportional to {displaystyle n^{3/2}} , where {displaystyle n} is the number of vertices in the graph, and the best known upper bound on the number of steps that suffice is larger, proportional to {displaystyle n^{2}} .[12] 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 {displaystyle K_{4}} 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.[13] Lifting Equilibrium stress on the graph of a cube A frustum lifting the stressed drawing (with the same 2d positions) into 3d 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.[14][15] 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.[16] 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.[17] 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.[4][18] 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.[19] Circle packing A polyhedron realized from a circle packing on the blue midsphere. Each polyhedron vertex is represented in the packing by its horizon circle (red). Each face is represented by the circle made by its intersection with the sphere.