Proving a non-planar graph is n-connected

Question

Say G is a non-planar graph with all degrees at least 3 such that every proper induced subgraph of G is a planar graph.

How may we prove that G must be 3-connected? Any help is appreciated.

Answer 1

I don't have a proof, just some more or less obvious ideas which you may have already thought of.

Since ${\sf G}$ is non-planar, it contains a (not necessarily induced) subgraph ${\sf H}$ which is a subdivision of a Kuratowski graph ${\sf K}$, either ${\sf K}={\sf K}_5$ or ${\sf K}={\sf K}_{3,3}$. Moreover, ${\sf H}$ is a spanning subgraph of ${\sf G}$; if some vertex $v$ of ${\sf G}$ were not in ${\sf H}$, then ${\sf G}-v$ would be non-planar. Thus ${\sf G}$ may be described as a subdivision of ${\sf K}$ with enough additional edges to make all vertex degrees at least $3$. Moreover, the fact that all subgraphs of the form ${\sf G}-v$ are planar imposes a restriction on where the additional edges can go. Namely, if ${\sf P}$ is a path in ${\sf G}$ corresponding to an edge of ${\sf K}$, then none of the additional edges can join two vertices of ${\sf P}$.

Now ${\sf K}$ itself is of course $3$-connected, and that is a special case of the theorem you are trying to prove. The subdivision graph ${\sf H}$ will not be $3$-connected, but it seems reasonable that the presence of a third edge incident with each subdivision point makes ${\sf G}$ $3$-connected. I haven't worked out a detailed proof of that. I guess you may have to consider some cases, and I'm not sure which characterization of $3$-connectedness will be the most convenient to work with.

I hope this helps.