1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please provide the graph in your post, and tell us which nodes you are identifying with $K_{3,3}$. $\endgroup$ – Théophile May 14 '15 at 18:52
3
$\begingroup$

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.

$\endgroup$

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.