0
$\begingroup$

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 Graph1



Solution Solution

  • 0
    Thanks for the feedback Michael2012-10-20

1 Answers 1

1

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} 
  • 0
    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.2012-10-22