# Kuratowski's theorem and non - planar graph

Hi I have attached two graphs. I am trying to prove that the graph is non- planar. By Kurathowski's theorem, a graph is nonplanar if and only if it contains a subgraph homeomorphic to $K_{3,3}$ or $K_5$. Therefore, I extracted the subgraph below which is homeomorphic to $K_{3,3}$. Does this look correct? Please can someone affirm the solution is correct?

Graph

Solution

• Looks good to me. – Michael Biro Oct 20 '12 at 19:08
• Thanks for the feedback Michael – bosra Oct 20 '12 at 19:23

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:

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}

• I'd like to add to Douglas' excellent answer the following minor point: Drawing embeddings in the plane of abstract graphs looks simpler then it really is-you should practice hand-drawing as many as you can-including their subgraphs, complements, duals,etc. – Mathemagician1234 Oct 22 '12 at 6:47