Kuratowski's theorem in every case?

634 Views Asked by At

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.

3

There are 3 best solutions below

1
On BEST ANSWER

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

1
On

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

1
On

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.