Last wins - DPChallenge Forums

Canon EF-S 10-22mm f/3.5-4.5 USM

10/19/2012 10:41:22 PM · #17326

I stand corrected,and I see the threads and views are as well,
also winning.

Message edited by author 2012-10-19 22:43:32.

cowboy221977

Canon EOS-60D

10/19/2012 10:44:30 PM · #17327

Originally posted by Cory:

Do you jackasses realize this thread is now at 258333 views and 17324 responses?

Hey Cory..the "last wins" thread is a pasttime...join us sometime you might have fun

Cory

Canon EOS-1D Mark IV

Canon EF 85mm f/1.2L II USM

10/19/2012 11:01:04 PM · #17328

Originally posted by cowboy221977:

Originally posted by Cory:
Do you jackasses realize this thread is now at ~~258333~~ 258345 views and ~~17324~~ 17327 responses?

Hey Cory..the "last wins" thread is a pasttime...join us sometime you might have fun

Meh, pasttime... Isn't it pastyourbedtime? ;)

I'm here to win, I thought about hiring hitmen, but that was just too expensive, so I'll just have to try to remind you where this thread stands. Perhaps I can be the ultimate thread killer.

Message edited by author 2012-10-19 23:04:23.

cowboy221977

Canon EOS-60D

Canon EF-S 10-22mm f/3.5-4.5 USM

10/19/2012 11:17:20 PM · #17329

thread killer...nah you're ok

beatabg

Google Pixel

10/20/2012 12:07:19 AM · #17330

Originally posted by Cory:

Do you jackasses realize this thread is now at 258333 views and 17324 responses?

I don't think I was ever called a jackass before, lol. Well if you didn't open the thread Cory it would have less views... just saying

cowboy221977

Canon EOS-60D

Canon EF-S 10-22mm f/3.5-4.5 USM

10/20/2012 12:22:19 AM · #17331

Originally posted by beatabg:

Originally posted by Cory:
Do you jackasses realize this thread is now at 258333 views and 17324 responses?

I don't think I was ever called a jackass before, lol. Well if you didn't open the thread Cory it would have less views... just saying

Good point

Canon EF 200mm f/2.8 L II USM Lens

10/20/2012 02:49:18 AM · #17332

Jack asses. LOL

skewsme

Canon EOS-6D

10/20/2012 06:06:54 AM · #17333

i can't believe no one wanted to play tinkertoys with the beev.

Originally posted by bvy:

Let G be a k-critical graph with k >= 2. Then G is (k-1)-edge connected.

Proof: The only 2-critical and 3-critical graphs are K2 (the complete graph on two vertices) and the odd cycles, respectively. Clearly K2 is 1-edge connected, and the odd cycles (all cycles, actually) are 2-edge connected. So we assume k >= 4.

Let G be a k-critical graph, and suppose it is not (k-1)-edge connected. Then we can partition the vertices of G into sets V1 and V2 such that the induced subgraphs G1 = G[V1] and G2 = G[V2] have at most (k-2) edges connecting them. Since G is k-critical, G1 and G2 are both necessarily (k-1)-critical. Let E be the edge set connecting vertices of G1 and G2. There should then be some edge in E that connects vertices of the same color -- for if there is not, then G could be properly colored with (k-1) colors and, as such, would not be k-critical. But this is the crux of our proof; by showing that it's possible to permute the colors of the vertices of G1 in such a way that every edge in E connects vertices of different colors, we arrive at the contradiction needed to complete our proof.

We start by partitioning the vertices of G1 by their assigned colors. There are at most (k-2) partitions that have neighbors in V2, and we denote these U1, U2, ..., U_t (t <= k-2). Let k_i be the number of edges in E incident with a vertex in U_i. Then 1 <= k_i <= (k-2), and the sum of all k_i is (k-2). Now consider the vertices of U1 that have neighbors in V2. If every such vertex has a different-colored neighbor, then we leave U1 alone. If, however, some vertex of U1 has a neighbor in V2 of the same color, then it is possible to permute the colors of the various U_i and assign U1 a color such that every vertex of U1 has a different colored neighbor in U2. This is possible because the vertices of U1 have at most (k-2) neighbors in V2, yet there are (k-1) possible colors to assign to U1.

Next we take U2. Again, if every vertex therein has a different-colored neighbor in G2, then we move on. If, though, some vertex of U2 has a like-colored neighbor in G2, then we permute the colors of the various U_i (i>=2) and assign U2 a color that erases any conflicts. This is possible because there are (k-1) - (k_2 + 1) colors to avoid, and (k-1) - (k_2 + 1) >= (k-1) - (k_2 + k_1) >= (k-1) - (k-2) = 1.

Continuing in this manner, we can find a (k-1)-coloring for G, which is the desired contradiction.

10/20/2012 09:00:54 AM · #17334

He didn't come up with the ...contradiction we desired. :P

beatabg

Google Pixel

10/20/2012 12:17:13 PM · #17335

Originally posted by Digipixer:

He didn't come up with the ...contradiction we desired. :P

That was exactly it..
:)

10/20/2012 12:52:57 PM · #17336

Originally posted by beatabg:

Originally posted by Digipixer:
He didn't come up with the ...contradiction we desired. :P

That was exactly it..
:)

Is that all it is? Well, if G is k-critical then we can't properly color the vertices of G with fewer than k colors. What I've shown is that if G is connected by fewer than (k-1) edges, that there is a (k-1) coloring of G. Proof by contradiction. I can't find another way to tackle it, but I suspect any other approach would be far less straightforward.

Sorry for the confusion.

10/20/2012 01:11:38 PM · #17337

K2 is more than 1-edge connected.

10/20/2012 01:45:40 PM · #17338

Originally posted by Digipixer:

K2 is more than 1-edge connected.

K2 has only one edge.

10/20/2012 01:59:25 PM · #17339

So we assume k >= 4.

Not so.

10/20/2012 02:24:08 PM · #17340

Originally posted by Digipixer:

So we assume k >= 4.

Not so.

We can assume k >= 4 because we explicitly covered the cases of k = 2 and k = 3. The criticially 2-chromatic graphs and critically 3-chromatic graphs are easily classified, whereas no known classifications exist for higher order k-chormatic graphs (i.e. k >= 4).

10/20/2012 04:33:36 PM · #17341

K=9

10/20/2012 05:42:14 PM · #17342

I'm a K9 hero. I just saved a dog and returned him home. True story.

10/20/2012 05:51:54 PM · #17343

Congrats! You deserve an award. ...and a break from this thread. Enjoy.

10/20/2012 05:53:08 PM · #17344

No break, thanks.

10/20/2012 06:03:01 PM · #17345

suit yourself.

10/20/2012 06:04:30 PM · #17346

I will.

10/20/2012 06:04:55 PM · #17347

If there are no more questions, we might be ready to move on to Brooks' Theorem.

10/20/2012 06:10:35 PM · #17348

Or not.

10/20/2012 06:47:01 PM · #17349

K=4 not K>4

Message edited by author 2012-10-20 18:49:48.