An -polyhedral graph (sometimes called a -net) is a 3-connected simple planar graph on nodes. Every convex polyhedron can be represented in the plane or on the surface of a sphere by a 3-connected planar graph. Conversely, by a theorem of Steinitz as restated by Grünbaum (2003, p. 235), every 3-connected planar graph can be realized as a convex polyhedron (Duijvestijn and Federico 1981). Polyhedral graphs are sometimes simply known as "polyhedra" (which is rather confusing since the term "polyhedron" more commonly refers to a solid with faces, not vertices).
The number of distinct polyhedral graphs having , 2, ... vertices are 0, 0, 0, 1, 2, 7, 34, 257, 2606, ... (OEIS A000944; Grünbaum 2003, p. 424; Duijvestijn and Federico 1981; Croft et al. 1991; Dillencourt 1992). Through duality, each polyhedral graph on nodes corresponds to a graph (and polyhedron) with faces. So the polyhedral graphs on nodes are isomorphic to the convex polyhedra with faces. There is therefore a single tetrahedral graph, two pentahedral graphs, etc., meaning also that there is a single tetrahedron, two pentahedra, etc.
There is no known formula for enumerating the number of nonisomorphic polyhedral graphs by numbers of edges , vertices , or faces (Harary and Palmer 1973, p. 224; Duijvestijn and Federico 1981). The numbers for the first few are summarized in the table below.
# | graph name | |
4 | 1 | tetrahedral graph |
5 | 2 | pentahedral graph |
6 | 7 | hexahedral graph |
7 | 34 | heptahedral graph |
8 | 257 | octahedral graph |
9 | 2606 | nonahedral graph |
10 | 32300 | decahedral graph |
Duijvestijn and Federico (1981) enumerated the polyhedral graphs on edges, obtaining 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, ... (OEIS A002840) for , 7, 8, ....
The smallest nonnamiltonian polyhedral graph is the Herschel graph, which has 11 nodes. The numbers of non-Hamiltonian polyhedral graphs on , 12, ... nodes are 1, 2, 30, 239, 2369, 22039, 205663, ... (OEIS A007030; Dillencourt 1991). Similarly, the numbers of non-Hamiltonian polyhedral graphs with , 10, ... faces are 1, 8, 135, 2557, ... (OEIS A007032; Dillencourt 1991).
There are no untraceable graphs polyhedral graphs on 13 or fewer nodes.