# Kuratowski's theorem in every case?

I have the following graph $G$ (from Chartrand and Zhang, page 235, figure 9.9) which is based on a maximal planar graph on 7 vertices with an additional edge (labeled $uv$). This graph is nonplanar because $m>3n-6$. Also, this graph does not contain either $K_{3,3}$ or $K_5$ as a subgraph (this is proved in the text). My question is why doesn't this contradict Kuratowski's theorem? Shouldn't there be a subdivision of one of these contained in $G$? But there are no vertices of degree two in this graph, so I'm not sure what subgraph I can take to build either of the critical graphs. I know the subgraph needs the edge $uv$, but that's all I know.

At this point in the text, contractions haven't been discussed, and subdivisions were just introduced, so I'm not sure how to proceed.

There is a subdivided $K_{3,3}$ embedded in this graph. Each of $u,z,s$ are connected to each of $v,t,y$ by distinct edges of your graph, except that $u$ and $y$ are connected the two edge path $uxy$.
• It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_{3,3}$ and then came back to find your answer - thank you! – Joshua Sasmor Jul 21 '18 at 18:07
$\{u,s,x,v,t\}$ forms a subdivision of $K_5$ in the graph. This can be formed by deleting the edges from $y$ and $z$ to $s$ and $t$, then smoothing out the path $xyzv$.
• Thank you - this was helpful - I found a $K_{3,3}$, but I wasn't sure about the $K_5$. – Joshua Sasmor Jul 21 '18 at 18:07
• Thank you - it calls for a "subdivision of $K_{3,3}$ or $K_5$" I wasn't sure how to find that. – Joshua Sasmor Jul 21 '18 at 18:06