KNOWPIA
WELCOME TO KNOWPIA

In geometric graph theory, a branch of mathematics, a **polyhedral graph** is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

The Schlegel diagram of a convex polyhedron represents its vertices and edges as points and line segments in the Euclidean plane, forming a subdivision of an outer convex polygon into smaller convex polygons (a convex drawing of the graph of the polyhedron). It has no crossings, so every polyhedral graph is also a planar graph. Additionally, by Balinski's theorem, it is a 3-vertex-connected graph.

According to Steinitz's theorem, these two graph-theoretic properties are enough to completely characterize the polyhedral graphs: they are exactly the 3-vertex-connected planar graphs. That is, whenever a graph is both planar and 3-vertex-connected, there exists a polyhedron whose vertices and edges form an isomorphic graph.^{[1]}^{[2]} Given such a graph, a representation of it as a subdivision of a convex polygon into smaller convex polygons may be found using the Tutte embedding.^{[3]}

Tait conjectured that every cubic polyhedral graph (that is, a polyhedral graph in which each vertex is incident to exactly three edges) has a Hamiltonian cycle, but this conjecture was disproved by a counterexample of W. T. Tutte, the polyhedral but non-Hamiltonian Tutte graph. If one relaxes the requirement that the graph be cubic, there are much smaller non-Hamiltonian polyhedral graphs. The graph with the fewest vertices and edges is the 11-vertex and 18-edge Herschel graph,^{[4]} and there also exists an 11-vertex non-Hamiltonian polyhedral graph in which all faces are triangles, the Goldner–Harary graph.^{[5]}

More strongly, there exists a constant (the shortness exponent) and an infinite family of polyhedral graphs such that the length of the longest simple path of an -vertex graph in the family is .^{[6]}^{[7]}

Duijvestijn provides a count of the polyhedral graphs with up to 26 edges;^{[8]} The number of these graphs with 6, 7, 8, ... edges is

- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (sequence A002840 in the OEIS).

One may also enumerate the polyhedral graphs by their numbers of vertices: for graphs with 4, 5, 6, ... vertices, the number of polyhedral graphs is

The graphs of the Platonic solids have been called *Platonic graphs*. As well as having all the other properties of polyhedral graphs, these are symmetric graphs, and all of them have Hamiltonian cycles.^{[9]} There are five of these graphs:

- Tetrahedral graph – 4 vertices, 6 edges
- Octahedral graph – 6 vertices, 12 edges
- Cubical graph – 8 vertices, 12 edges
- Icosahedral graph – 12 vertices, 30 edges
- Dodecahedral graph – 20 vertices, 30 edges

A polyhedral graph is the graph of a simple polyhedron if it is cubic (every vertex has three edges), and it is the graph of a simplicial polyhedron if it is a maximal planar graph. For example, the tetrahedral, cubical, and dodecahedral graphs are simple; the tetrahedral, octahedral, and icosahedral graphs are simplicial.

The Halin graphs, graphs formed from a planar embedded tree by adding an outer cycle connecting all of the leaves of the tree, form another important subclass of the polyhedral graphs.

**^**Ziegler, Günter M. (1995), "Chapter 4: Steinitz' Theorem for 3-Polytopes",*Lectures on Polytopes*, Springer, pp. 103–126, ISBN 0-387-94365-X**^**Grünbaum, Branko (2003),*Convex Polytopes*, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, ISBN 978-0-387-40409-7.**^**Tutte, W. T. (1963), "How to draw a graph",*Proceedings of the London Mathematical Society*,**13**: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387.**^**Barnette, David; Jucovič, Ernest (1970), "Hamiltonian circuits on 3-polytopes",*Journal of Combinatorial Theory*,**9**(1): 54–59, doi:10.1016/S0021-9800(70)80054-0**^**Goldner, A.; Harary, F. (1975), "Note on a smallest nonhamiltonian maximal planar graph",*Bull. Malaysian Math. Soc.*,**6**(1): 41–42**^**Grünbaum, Branko; Motzkin, T. S. (1962), "Longest simple paths in polyhedral graphs",*Journal of the London Mathematical Society*, s1-37 (1): 152–160, doi:10.1112/jlms/s1-37.1.152**^**Owens, Peter J. (1999), "Shortness parameters for polyhedral graphs",*Discrete Mathematics*,**206**(1–3): 159–169, doi:10.1016/S0012-365X(98)00402-6, MR 1665396**^**Duijvestijn, A. J. W. (1996), "The number of polyhedral (3-connected planar) graphs" (PDF),*Mathematics of Computation*,**65**(215): 1289–1293, doi:10.1090/S0025-5718-96-00749-1.**^**Read, Ronald C.; Wilson, Robin J. (1998), "Chapter 6: Special graphs",*An Atlas of Graphs*, Oxford Science Publications, Oxford University Press, pp. 261, 266, ISBN 0-19-853289-X, MR 1692656

- Weisstein, Eric W., "Polyhedral Graph",
*MathWorld*