Graph Theory – Proof that Every Polyhedral Graph is Planar

graph theoryplanar-graphs

Every graph theory book or internet resource on graph theory says the graph of a convex polyhedron is planar, i.e. it can be drawn on a plane without edges crossing.

Graph of a convex polyhedron is constructed by drawing vertices of the polyhedron and connecting the pairs that are connected by an edge in the polyhedron. Unfortunately I can't find a formal proof of this theorem. There are some vague explanations based on intuition, Schlegel's diagram, but there's no true, complete, formal proof, or at least I didn't come across one. A proof that makes it obvious, guarantees and makes the reader confident that there is no single special case where the theorem doesn't hold.

If you can at least point a book title or any other resource where a proper proof is given, please do. Thanks for help.

Best Answer

I don't know for sure what would qualify as a formal proof.

How about: Embed the graph in a sphere (since the polyhedron is convex, choose a sphere whose center is inside the polyhedron; and then radially project vertex points and edge points so that they lie on the sphere); then orient the sphere so that the north pole is not a vertex or on an edge of the embedded graph; and then stereographically project the sphere, along with the embedded graph, onto the horizontal plane through the south pole.

Related Question