Last wins - DPChallenge Forums

12/13/2010 02:50:12 PM · #4426

Ahem. Attention KMart threadjackers: Meetup threads are on aisle five.

TrollMan

Fujifilm X-T4

Fujifilm XF 35mm f/1.4

12/13/2010 03:24:54 PM · #4427

Right you are. Back to business: I win!

Nikon AF-S DX NIKKOR 18-200mm f/3.5-5.6G ED VR II

12/13/2010 03:28:18 PM · #4428

If I may be permitted to indirectly quote the great Art Roflmao on this one: "not."
That is all.

Ja-9

Nikon D750

12/13/2010 03:34:37 PM · #4429

oh, and so ya'll think you've won...NOT!!! (and not KNOT)

12/13/2010 03:40:24 PM · #4430

The Petersen Graph, as it turns out, is not a planar graph. This is a well known and established fact. However, being unfamiliar with the problem before recently, I conjectured (incorrectly) that it was planar. More later.

12/13/2010 04:33:31 PM · #4431

Attention students: Math class is over in building H. That is all.

12/13/2010 04:58:06 PM · #4432

There's a bunch of screwballs in Building H eating cake.

Anyway, there's a theorem that says that a graph is planar if and only if it contains neither K5 nor K(3,3) as a subgraph, nor any subdivision thereof.

Since each vertex of the Petersen graph has degree 3, it's easy to see that K5 cannot be a subgraph. (Each vertex of K5 has degree 4.)

Further, K(3,3) itself cannot be a subgraph of the Petersen graph. Before I continue, can anyone see why?

Nikon AF-S DX Zoom-Nikkor 18-55mm f/3.5-5.6 ED

12/13/2010 05:11:31 PM · #4433

Originally posted by bvy:

Anyway, there's a theorem that says that a graph is planar if and only if it contains neither K5 nor K(3,3) as a subgraph, nor any subdivision thereof.

Since each vertex of the Petersen graph has degree 3, it's easy to see that K5 cannot be a subgraph. (Each vertex of K5 has degree 4.)

Further, K(3,3) itself cannot be a subgraph of the Petersen graph. Before I continue, can anyone see why?

f*** it, you win.

Apple iPhone 5

12/13/2010 07:24:33 PM · #4434

010010010010000001110111011010010110111000100001

Nikon AF-S DX NIKKOR 18-200mm f/3.5-5.6G ED VR II

12/13/2010 07:51:14 PM · #4435

Since no one knows, it's because K(3,3) contains C4, a cycle of length 4 -- three of them actually. The Petersen graph contains no such cycle.

I'm looking at this again, and think that perhaps a subdivision of K5 can be found in the Petersen graph.

I'll post back soon.

Ja-9

Nikon D750

12/13/2010 10:35:39 PM · #4436

HUH....

fotomann_forever

12/14/2010 12:17:28 AM · #4437

Someone said C-4? Ohhhh that stuff is so much fun to play with...

12/14/2010 12:46:31 AM · #4438

TrollMan

Fujifilm X-T4

Fujifilm XF 35mm f/1.4

12/14/2010 03:19:47 AM · #4439

C2H5OH is MUCH better. I had some least weekend.

12/14/2010 05:33:11 AM · #4440

delta 9 tetrahydrocannabinol is MUCH better. I had some least weekend!

TrollMan

Fujifilm X-T4

Fujifilm XF 35mm f/1.4

12/14/2010 05:44:37 AM · #4441

Not for me but I guess culture in the Netherlands. Nevertheless I win! :P

12/14/2010 05:51:18 AM · #4442

blow up a hill, blow up a building, eat a twinky... different strokes for different folks! (its all the same and can only mean one thing...) I WIN!

Nikon AF-S DX Zoom-Nikkor 18-55mm f/3.5-5.6 ED

12/14/2010 12:08:03 PM · #4443

Life is made up of moments and in life there are winners and losers. At this moment I am the winner.

Apple iPhone 5

12/14/2010 12:39:50 PM · #4444

Art, that's a beautiful sentiment. Long may you reign.

fotomann_forever

12/14/2010 01:04:48 PM · #4445

Originally posted by Art Roflmao:

Life is made up of moments and in life there are winners and losers. At this moment I am the winner.

Oh, now we see who is hogging all the delta 9 tetrahydrocannabinol.

12/14/2010 01:44:21 PM · #4446

Yeah, I've been hanging out with a friend of mine.

12/14/2010 03:33:03 PM · #4447

Seems there are some class clowns among us.

The resource I'm referencing (Chartrand) states the theorem of planarity in terms of a graph having K5 or K(3,3) or a subdivision of one of these graphs as a subgraph (casually stated). This, I believe, is Kuratowski's theorem.

Another theorem, this one attributed to Wagner, states that a graph is planar if and only if it does not have K5 or K(3,3) as a minor.

The difference is that Wagner's Theorem takes edge deletions and edge contractions into consideration (from the definition of a graph minor), while Kuratowski speaks only in terms of subdivisions.

Seems to me that the Petersen graph fails Kuratowski on the K5 test, but passes Wagner.

Excuse me a moment...

12/14/2010 03:36:44 PM · #4448

wait a tic! It passes Wagner stadium? Nah! Sophie Polkamp plays there, trust me, it would not pass Wagner, not on a Sunday! (next post wins!)

12/14/2010 03:37:15 PM · #4449

I win!