So, I saw this graph of 10 vertices. I then thought to myself

https://en.wikipedia.org/wiki/Planar_graph

You can find ways to prove this in this article.

>>7850301
Me again.

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.

>>7850291
You'll need topology. Graph theory stops just short of being able to say things about the structure of a given graph. As far as I know, anyway.

>>7850308
But then again, there are still graphs that are non planar and still does not contain a Kuratowski subgraph. So, it can be frustrating to prove this.

>>7850315
do you know what if and only if means?

>>7850320
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.

File: 1420865582332.jpg (37KB, 662x413px) Image search: [Google]

37KB, 662x413px

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

>>7850291

Isn't that just the petersen graph?

It has crossing number 1. You can get a proof from how kuratowski's theorem.

>>7850311

Wasn't kuratowski's theorem known for not involving topological things, and instead involving some long prove with a bunch of cases?

>>7850393
>some long proof with a bunch of cases
Isn't that the same thing as informal topology?

>>7850415

I mean that it succeeded (with a pretty simple condition, too), where the other more topological proofs failed and never worked.

Wtf are you autists on about

>>7850497
If you can't figure that out by reading the thread, you don't belong on /sci/. Try >>>/b/, >>>/soc/, or possibly even >>>/lit/.

File: donut.jpg (52KB, 734x467px) Image search: [Google]

52KB, 734x467px

>>7850291

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.

Deleting the E-D and A-C edges gives you a Kuratowski graph (based on K3,3). {G, I, B} is one partite set and {J, F, H} is the other.

>>7850291
It has Euler characteristic 3, so it can't be planar.

>>7850671
>>7850724
/thread

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.

>>7850514
Hah

>>7850514
That fits the rules too

File: graph.jpg (15KB, 405x182px) Image search: [Google]

15KB, 405x182px

>>7852330

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?

>>7852852
oh yeah right. You probably need to find a subgraph homeomorphic to K_5 or K_3_3 then.

>>7852904

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.

>>7850291
I'm probably not understanding this correctly, but wouldn't it work if F was moved down to the edge between J and C?

>>7853467

then how do you draw edges AF and GF
without crossing any other?