Determine whether my graph is planar or not

Question

As I think this is not a planar graph. First I deleted the $cd$ edge and kept vertex $b$ onto vertex $e$ then I got a subgraph $K_5$ with vertex $gcade$.Is it correct? Can anyone verify the answer?

Answer 1

I'm not sure where you see $K_5$. Here's an alternative argument.

Delete vertex $f$ and all edges connected to it. Delete vertex $dg$. We show that the obtained graph is not planar.

Start by drawing the cylce $adegh$. Next, we wish to place $c$. Without loss, place it inside the cycle. Draw the edges connecting the cycle with $c$.

As $bc$ needs to be drawn, also $b$ is inside the cycle. Either

• you draw $b$ inside $acgh$, in which case the edge $be$ will cross another edge,
• or you draw $b$ inside $acd$, in which case the edge $be$ will cross another edge,
• or you draw $b$ inside $cged$, in which case $ab$ crosses another edge.

None of the cases work, proving non-planarity or your graph.

Answer 2

Mathematica:

gg = Graph[{
   a \[UndirectedEdge] b, a \[UndirectedEdge] d, 
   a \[UndirectedEdge] h, a \[UndirectedEdge] c, 
   b \[UndirectedEdge] c, b \[UndirectedEdge] e, 
   c \[UndirectedEdge] d, c \[UndirectedEdge] g, 
   d \[UndirectedEdge] e, d \[UndirectedEdge] f, 
   d \[UndirectedEdge] g, e \[UndirectedEdge] f, 
   e \[UndirectedEdge] g, f \[UndirectedEdge] g, 
   g \[UndirectedEdge] h},
  VertexLabels -> "Name"]

PlanarGraphQ[gg]

(* False *)

Answer 3

Let us start by recalling Kuratowski's theorem https://en.wikipedia.org/wiki/Kuratowski%27s_theorem

So if we can merge distinct blocks of vertices (preserving adjacency in the obvious way) and form $K_5$ or $K_{3,3}$ then a graph is non planar.

The partition $\{ \{a\},\{c\},\{d\},\{e,b\},\{f,g,h\}\}$ is a subgraph that is isomorphic to $K_5$. So your graph is $\color{red}{\text{not}}$ planar.

Answer 4

Here is another way to establish that your graph is not planar. Delete the vertex $f$ and edges $dg$ and $ac$. Then remove vertex $h$ and add edge $ag$. As a result, we obtain graph $K_{3,3}$ with the parts $\{a,c,e\}$ and $\{b,d,g\}$