Prove that if $G$ does not contain a subdivision of $K_{3,3}$ then $G$ is planar.

Question

Let $T$ be a tree of order at least $5$, and let $e_1,e_2,\cdots,e_5 \in E(T)$. Let $G = T + \{e_1,e_2,\cdots,e_5\}$.

Prove that if $G$ does not contain a subdivision of $K_{3,3}$ then $G$ is planar.

Answer 1

We first claim that the resulting grtaph $G$ caNNOT have a subdividion of $K_5$, even if $G$ is nonplanar. Indeed, if $G$ has a subdivision of $K_5$ then there is a subgraph $G'$ of $G$ that has $x$ vertices (for some $x$) and $x+5$ edges. Indeed, 5 of the vertices have degree 4 and the remaining $x-5$ vertices have degree 2. But as $T$ is a tree and only 5 edges were added, this is impossible, as $G'$ can have at most $x+4$ edges (indeed, $G' \setminus \{e_1,e_2,e_3,e_4,e_5\}$ is a tree or forest (as it is a subgraph of a tree) so at most $x-1$ edges in $G' \setminus \{e_1,e_2,e_3,e_4,e_5\}$). So indeed, $G$ caNNOT have a suibdividion of $K_5$, even if $G$ is nonplanar.

Thus from the above paragraph and Kuratowski's Thm, $G$ is nonplanar iff $G$ has a subdivision of $K_{3,3}$.