Trouble determining planarity of graph

77 Views Asked by At

I am practicing for an exam and I can not wrap my head around this exercise. I am supposed to show if the given graph is planar by drawing it or show the subgraph that is homeopathic to K 3,3 or K5.

The graph in question The graph in question

I believe it is non-planar and can be reduced to K5 but besides eliminating e(h,e) I can't find the rest of the edges to eliminate.

1

There are 1 best solutions below

3
On

Vertices $b,c,d$ are all adjacent to $a,f,g$ except for $c$ to $a$, for which you can go via $i$, and $g$ to $d$, for which go via $h$ and $e$. So the graph contains a subgraph which is homeomorphic to $K_{3,3}$, and so the graph is not planar.

See also my answer to this very similar recent question.

Edit. In fact, the vertices $a,d,e,h,i$ are all adjacent except for $d,h$ where we can go via $b$ and $g$, and $d,i$ where we can go via $f$ and $c$. So there is also a subgraph homeomorphic to $K_5$.