So, I saw this graph of 10 vertices. I then thought to myself "Huh, no matter how you arrange these 10 vertex there will always be at least one place where two edges cross".
But this thought has now been bothering me all day. My issue being I am pretty damn certain this is true but have no way to write a formal math proof. So how could I go about doing that so I can turn my hand waving intuitive nonsense into something more substantial.
use Kuratowski's Theorem.
" The graph G is planar if and only if it does not contain a Kuratowski subgraph."
So the simplest way would be to find a kuratowski subgraph inside the graph.
A complete K5 och K3 graph is a such a graph.
The proof of the theorem can be find on the net.
Yeah, I am tired...
Actually meant that even if you could not find a K3,3, or K5 you have not proven that it is a planar graph, however he wants to prove that it is a non-planar graph.
i once had to prove the planarity of a graph without using any previously established "easy" theorems (the kuratowski and wagner stuff)
i was not ready
i don't see where your problem is.
here: have a donut with your solution on it.
no need to thank me, just doing mah job, ma'am.
Assuming I counted right it has 10 vertices, 15 edges and 8 regions so v - e + r = 10 - 15 + 8 = 3 != 2 so the graph can't be planar. Note in general that this is just a sufficient condition for the graph being nonplanar but not a necessary one.
the r count is a bit weird. when edges cross with no vertex at the intersection, are you sure you're supposed to count regions as you do?
here's an example with a very planar graph:
v=2, e=2, and as you count them, r=3...
euler characteristic still =3
to make it short, it seems to depend on the picture of a graph, not on the graph itself...
tl,dr: how do you count regions?
There are many other ways to prove non-planarity though, such as arguments for degrees, etc.
However for proving the petersen graph (OP's graph) is non-planar, just look for K3,3 in it.