# Prove that graph is non-planar

Let's say I have a graph like this

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)?

• How can you prove that the following formula is red: $\color{red}{y=x\ }$? – Mark McClure Oct 25 '17 at 12:51
• @Arthur I changed the picture, sorry for that. – 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.