3
$\begingroup$

I have the following graph $G$ (from Chartrand and Zhang, page 235, figure 9.9) figure 9.9, a nonplanar graph

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.

$\endgroup$
5
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Joshua Sasmor Jul 21 '18 at 18:07
5
$\begingroup$

$\{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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you - this was helpful - I found a $K_{3,3}$, but I wasn't sure about the $K_5$. $\endgroup$ – Joshua Sasmor Jul 21 '18 at 18:07
1
$\begingroup$

Check again the statement of Kuratowski's theorem. It does not talk about subgraphs, but some kind of graph minors. This example is a perfect illustration why Kuratowski's theorem SHOULD NOT talk about subgraphs.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you - it calls for a "subdivision of $K_{3,3}$ or $K_5$" I wasn't sure how to find that. $\endgroup$ – Joshua Sasmor Jul 21 '18 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.