Polyhedral Graph

A polyhedral graph (sometimes called a -net) is a 3-connected simple planar graph. An -polyhedral graph has vertices. 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 numbers of distinct polyhedral graphs having , 2, ... vertices are 0, 0, 0, 1, 2, 7, 34, 257, 2606, ... (OEIS A000944; Duijvestijn and Federico 1981; Croft et al. 1991; Dillencourt 1992; Grünbaum 2003, p. 424). Through duality, each polyhedral graph on nodes corresponds to a graph (and polyhedron) with faces. This gives a bijection between isomorphism classes. A graph need not be isomorphic to its dual graph. For example, the cubical graph has eight vertices and six faces, while its dual graph, the octahedral graph, has six vertices and eight faces.

The names pentahedral, hexahedral, heptahedral, octahedral, nonahedral, and decahedral graph have been used for the vertex count classes from five through ten (Gayathri 2018, pp. 50-51). Explicit vertex count names distinguish these classes from the skeletons of polyhedra named by their numbers of faces and from the Platonic graphs.

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	polyhedral 4-vertex graph
5	2	polyhedral 5-vertex graph
6	7	polyhedral 6-vertex graph
7	34	polyhedral 7-vertex graph
8	257	polyhedral 8-vertex graph
9	2606	polyhedral 9-vertex graph
10	32300	polyhedral 10-vertex 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 nonhamiltonian polyhedral graphs have 11 vertices. One example is the Herschel graph. The numbers of nonhamiltonian polyhedral graphs on , 12, ... vertices are 74, 1600, 43984, 1032208, 22960220, ... (OEIS A007033). The numbers of nonhamiltonian maximal planar graphs, corresponding to simplicial polyhedra, on , 12, ... vertices are 1, 2, 30, 239, 2369, 22039, 205663, ... (OEIS A007030; Dillencourt 1992). The unique 11-vertex example in this subclass is the Goldner-Harary graph. The numbers of nonhamiltonian polyhedral graphs with , 10, ... faces are 1, 8, 135, 2557, ... (OEIS A007032; Dillencourt 1992).

There are no untraceable polyhedral graphs on 13 or fewer vertices.

As shown by Whitney (1932), polyhedral graphs are uniquely embeddable (Fleischner 1973).