I'm trying to figure out how to show that two nonadjacent vertices in the graph of a convex polyhedron can be disconnected from one another by the removal of at least three vertices.
I know what a convex polyhedron is (I at least have a clear picture in my head of what they look like), and it is clear that they are planar, but I can't quite characterize them to even begin to prove this. I want to try assuming that the removal of two vertices would disconnect two nonadjacent vertices, but I can't see what to do from there. Any help or suggestions would be appreciated.
An n-polyhedral graph (sometimes called a c-net) is a 3-connected simple planar graph on n nodes. Every convex polyhedron can be represented in the plane or on the surface of a sphere by a 3-connected planar graph. Conversely, every 3-connected planar graph can be realized as a convex polyhedron. Polyhedral graphs are sometimes simply known as "polyhedra" (which is rather confusing since the term "polyhedron" more commonly refers to a solid with n faces, not n vertices). Through duality, each polyhedral graph on $V=n$ nodes corresponds to a graph with F=n faces. So the polyhedral graphs on n nodes are isomorphic to the convex polyhedra with n faces. The icosahedral graph with $12$ vertices is 5-connected and corresponds to the dodecahedron, a convex polyhedron with $12$ faces which is 3-connected. In every case either the polyhedral graph or its planar dual would be 3-connected.