In polytope theory, the edge graph (also known as vertex-edge graph or just graph) of a polytope is a combinatorial graph whose vertices and edges correspond directly to the vertices and edges of the polytope. As a purely combinatorial object, the edge graph encodes incidence information, capturing which vertices are connected by edges, but it does not retain geometric data such as vertex positions or edge lengths. Further common names for the edge graph are skeleton and 1-skeleton, though some authors reserve these terms for the geometric embedding formed by the vertices and edges in the polytope's ambient space. There is no universally agreed upon notation for the edge graph of a polytope P {\displaystyle P} . Common notations include G P {\displaystyle G_{P}} , G ( P ) {\displaystyle G(P)} or skel ( P ) {\displaystyle \operatorname {skel} (P)} . Not all graphs are realizable as edge graphs of polytopes; those that are realizable in this manner are called polytopal graphs. Edge graphs of 3-dimensional polytopes are also called polyhedral graphs. The problem of deciding whether a given graph is polytopal or not is known as the realization problem and is NP hard in general dimension. In dimension three the problem is also called the Steinitz problem in recognition of its resolution by Ernst Steinitz. Information about the polytope's faces of dimension two or higher is not immediately accessible from the edge graph, and often cannot be reconstruction from it at all. To capture the full combinatorial structure of a polytope, including the number of faces of each dimension and the incidence relations between them, one needs to work with the polytope's face lattice. In analogy to the term "1-skeleton", the part of the face lattice that contains the information about the combinatorics of faces up to dimension k {\displaystyle k} is called the k {\displaystyle k} -skeleton of the polytope.
General properties The edge graph of a convex polytope is a finite simple graph. It is connected, since a path between any two vertices can be obtained from the simplex algorithm. For low-dimensional polytopes the structure of the edge graph is essentially determined by the polytope's dimension:
the only 0-dimensional polytope is the point; its edge graph is K 1 {\displaystyle K_{1}} . the only 1-dimensional polytope is the line segment; its edge graph is K 2 {\displaystyle K_{2}} . the 2-dimensional polytopes are polygons. The edge graph of an n {\displaystyle n} -sided polygon is C n {\displaystyle C_{n}} , the cycle with n {\displaystyle n} vertices. the edge graphs of 3-dimensional polytopes are rich in structure but well-understood: by Steinitz's theorem the edge graphs of 3-polytopes are precisely the 3-vertex-connected planar graphs, for this reason also known as polyhedral graphs. For d {\displaystyle d} -polytopes with d ≥ 4 {\displaystyle d\geq 4} no characterization of edge graphs is known. Some general statements can be made:
the edge graph has minimum degree at least d {\displaystyle d} . If every vertex of a d {\displaystyle d} -polytope has degree exactly d {\displaystyle d} (i.e. the edge graph is d {\displaystyle d} -regular), then the polytope is said to be simple. the edge graph is d {\displaystyle d} -vertex connected. This is known as Balinski's theorem. the edge graph contains a subdivision of the complete graph K d + 1 {\displaystyle K_{d+1}} . In particular, for d ≥ 4 {\displaystyle d\geq 4} , the edge graph contains a K 5 {\displaystyle K_{5}} -minor and is not planar. It is in general non-trivial to determine whether a given graph is the edge graph of a polytope, that is, whether it is a polytopal graph. For some graph classes, such as graphs of minimum degree δ ≤ 3 {\displaystyle \delta \leq 3} , the above properties can help to decide this question. For example, the Petersen graph is 3-regular. Hence, if it were polytopal, it would be the edge graph of a 3-dimensional polytope. The Petersen graph is however not planar and thus cannot be the edge graph of a 3-polytope. For graphs of minimum degree δ ≥ 4 {\displaystyle \delta \geq 4} such questions are generally much harder to answer. For example, as of July 2025 it is unknown whether the Cartesian graph product of two Petersen graphs is polytopal. It is known that if it were polytopal, then the polytope must be of dimension four or five.
Examples
… excerpt ends here. Continue reading the full article.
