I've been trying to find out if this graph is planar or not for a while and have really been coming up short when it comes to creating a planar drawing of the graph. My intuition is telling me that it's non-planar, but I cannot find any subgraph of the graph homeomorphic to K3, 3 (by Kuratowski's Theorem). Any help would be greatly appreciated. The graph can be seen below:
Graph Theory – Is This Graph Planar?
graph theoryplanar-graphs
Related Solutions
I turned in my proof and the teacher said it is correct, so here it is again:
Assume the contrary, let there exist such a graph $G$. Since $G$ is planar, we can build a graph $G^*$ dual to $G$. Any two faces in $G$ share an edge $\implies$ any two faces in $G$ are adjacent $\implies$ any two vertices in $G^*$ are also adjacent (by the property of dual graphs). Since $G$ has 5 faces, $G^*$ has 5 vertices. So, $G^*$ is a complete graph on five vertices which might contain loops and parallel edges. Obviously, $K_5$ is a subgraph of $G^*$. Therefore, by Kuratowski's theorem, $G^*$ cannot be planar, which contradicts the property of dual graphs (a graph dual to a planar graph is also planar). Q.E.D.
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}
Best Answer
Although the question has already been thoroughly answered, here is an unusual approach to checking if a graph is planar that I'm very fond of which works well here.
First, we notice that there's a cycle passing through all $12$ vertices:
(This method is only guaranteed to settle the question one way or the other if we find such a cycle, though for a cycle that passes through only most of the vertices it can still be very helpful.)
Now redraw the graph so that this cycle is arranged in a circle:
If there's a planar embedding of the graph, this circle has to appear in it somewhere, and so the only choices left to make for how to draw the graph are deciding, for each edge not in the cycle, whether it will be drawn as a chord inside the circle or outside the circle.
But the three highlighted edges all intersect each other. No matter which choices you make for them, either two of them will be on the inside (and intersect) or two of them will be on the outside (and intersect). So there is no planar embedding.
(In general, once the Hamiltonian cycle has been found - if it exists - deciding if the remaining edges can be drawn without crossing is straightforward. Begin with an arbitrary choice and then just make sure that if an edge is on the inside, all the edges it crosses are on the outside, and vice versa.)