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.
As shown by Whitney (1932), polyhedral graphs are uniquely embeddable (Fleischner 1973).
-Nets of Orders 8 to 19, Inclusive, 2 vols. Unpublished
manuscript. Eindhoven, Netherlands: Philips Research Laboratories, 1960.Croft,
H. T.; Falconer, K. J.; and Guy, R. K. §B15 in