Decide if this cubic graph on 8 vertices is planar

326 Views Asked by At

Because I couldn't count faces and carry out Euler's formula for planar graphs I decided to "find" the $K_{3,3}$ subgraph in this way I'm not sure is how we're supposed to do it.

Given this graph (from here):

enter image description here

I begin by labelling the graph and noting its neighborhoods, I then "merge" three nodes together and get $K_{3,3}$ - is this how its supposed to be done?

I conclude that this graph is not planar.

1

There are 1 best solutions below

0
On BEST ANSWER

As in the graph you provide, contract $C=\{1,2,3\}$, you will directly get a $K_{3,3}$ with parts $\{C,5,7\}$ and $\{4,6,8\}$. Therefore, it is not planar.