[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y ] [Search | Home]
So, I saw this graph of 10 vertices. I then...
Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

File: graph.png (7 KB, 483x356) Image search: [iqdb] [SauceNao] [Google]
7 KB, 483x356
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.
>>
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 (37 KB, 662x413) Image search: [iqdb] [SauceNao] [Google]
37 KB, 662x413
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 (52 KB, 734x467) Image search: [iqdb] [SauceNao] [Google]
52 KB, 734x467
>>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
>>
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 (15 KB, 405x182) Image search: [iqdb] [SauceNao] [Google]
15 KB, 405x182
>>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?