Steinitz's Theorem

A Graph $G$ is the edge graph of a Polyhedron Iff $G$ is a Simple, Planar Graph which is 3-connected.

See also Planar Graph, Simple Graph