Let's say I have a graph like this

enter image description here

How can I prove that this graph is planar(or non-planar)?

According to Kuratowski's theorem: Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 or K3,3.

So I need to find if this graph containts subgraphs K(5) or K(3,3)?

And if I need to add few edges to make in non-panar, does it mean that I need to add edges to get either subgraph K(5) or K(3,3)?

  • $\begingroup$ How can you prove that the following formula is red: $\color{red}{y=x\ }$? $\endgroup$ – Mark McClure Oct 25 '17 at 12:51
  • $\begingroup$ @Arthur I changed the picture, sorry for that. $\endgroup$ – AlexMIEL Oct 25 '17 at 12:57

If you merge the two upper right vertices, and merge the two lower right vertices, you get $K_{3, 3}$. So the graph is not planar.

In general, you just have to search to see whether you can find $K_5$ or $K_{3,3}$, or whether you can find a planar embedding. I don't think there is some easy criterion that you can use to simply count up and conclude.


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.