Critical Nonplanar Graphs

232 Views Asked by At

In Alan Tucker's Applied Combinatorics, it is stated that "A graph G is critical nonplanar if G is nonplanar but any subgraph obtained by removing a vertex is planar."

The question is "Show that critical nonplanar graphs must be connected and cannot have a vertex whose removal disconnects the graph."

I am not sure how to show this, I have an example of a case where a vertex is removed, resulting in a planar graph, but is there something in the definition of a planar graph that it has to be connected?

1

There are 1 best solutions below

4
On

The deal is that if you have more than one component, then either one or more of the components are non-planar. To see this, suppose $G=G_1\cup G_2,$ such that the is no edge connecting any vertex of $G_1$ to $G_2$ and suppose further that $G_1$ is non-planar, then take any vertex of $G_2$ and is going still to be non-planar. What happens now if there is such vertex that disconnects the graph? It does not belong to a cycle(why?), so when you disconnect it, one of the parts is going to be non-planar. Can you show this?