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

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

Thread images: 4

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.

>>

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

>>

>>

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

>>

>>

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

>>

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

>>

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

Thread images: 4

Thread DB ID: 513439

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's