Kuratowski’s theorem in every case

graph theoryplanar-graphs

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.

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

Related Solutions

[Math] Kuratowski’s theorem and non – planar graph

Affirmed.

I offer the following (hopefully constructive) criticisms:

You should recognise why this graph drawing is important, e.g. by writing:

"We can see that the original graph has a subgraph homeomorphic to $K_{3,3}$ by redrawing it as follows: [[blah blah blah]]. Therefore it's not planar by Kuratowski's Theorem."

There's (arguably) a better way to draw the second graph; see below:

Original graph

New graph drawing

These were drawn using TikZ. Here's the LaTeX code:

\begin{tikzpicture}
  \tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
  \draw (0,0) node (c){};

  \draw (c)++(0*360/4+135:3) node[vertex] (A){$A$};
  \draw (c)++(1*360/4+135:3) node[vertex] (C){$C$};
  \draw (c)++(2*360/4+135:3) node[vertex] (D){$D$};
  \draw (c)++(3*360/4+135:3) node[vertex] (B){$B$};

  \draw (c)++(0*360/4+135:1.5) node[vertex] (E){$E$};
  \draw (c)++(1*360/4+135:1.5) node[vertex] (G){$G$};
  \draw (c)++(2*360/4+135:1.5) node[vertex] (H){$H$};
  \draw (c)++(3*360/4+135:1.5) node[vertex] (F){$F$};

  \draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
  \draw[ultra thick] (A) -- (E) -- (H) -- (D);
  \draw[ultra thick] (B) -- (F) -- (G) -- (C);
  \draw[ultra thick] (E) -- (G);
  \draw (F) -- (H);
\end{tikzpicture}

and for the second drawing:

\begin{tikzpicture}
  \tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
  \draw (0,0) node (c){};

  \draw (c)++(0,3)++(2,0) node[vertex] (G){$G$};
  \draw (c)++(0,3) node[vertex] (A){$A$};
  \draw (c)++(0,3)++(-2,0) node[vertex] (D){$D$};

  \draw (c)++(-2,0) node[vertex] (E){$E$};
  \draw (c) node[vertex] (C){$C$};
  \draw (c)++(2,0) node[vertex] (B){$B$};

  \draw (c)++(-2,1.5) node[vertex] (H){$H$};
  \draw (c)++(2,1.5) node[vertex] (F){$F$};

  \draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
  \draw[ultra thick] (A) -- (E) -- (H) -- (D);
  \draw[ultra thick] (B) -- (F) -- (G) -- (C);
  \draw[ultra thick] (E) -- (G);
  \draw (F) -- (H);
\end{tikzpicture}

[Math] Planar and non-planar graphs, and Kuratowski’s Theorem

Let's take bipartite graph $K_{3,3}$ with vertices $\{2,5,7\}$ in the first part and $\{1,3,6\}$ in the other and with edges: $(2,1); (2,3); (2,6); (5,1);(5,3);(5,6);(7,1);(7,3);(7,6)$. Next, in order to get $G_4$ graph we subdivide two edges: (5,3) and (7,1). It means that add new vertex on this edge. We add vertex 4 on the first edge and vertex 8 on the second. Now we don't have an $edge$ between vertices 5 and 3, but we have a $path$ between them. This is exactly what subdivision means. Then you can consider next two graphs in an analogous way.

Best Answer

Related Solutions

[Math] Kuratowski’s theorem and non – planar graph

[Math] Planar and non-planar graphs, and Kuratowski’s Theorem

Related Question