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

$\endgroup$
  • 3
    $\begingroup$ Looks good to me. $\endgroup$ – Michael Biro Oct 20 '12 at 19:08
  • $\begingroup$ Thanks for the feedback Michael $\endgroup$ – bosra Oct 20 '12 at 19:23
1
$\begingroup$

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}
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mathemagician1234 Oct 22 '12 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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