Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Looks good to me. –  Michael Biro Oct 20 '12 at 19:08
    
Thanks for the feedback Michael –  bosra Oct 20 '12 at 19:23

1 Answer 1

up vote 1 down vote accepted

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}
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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