Diablo® III

Graph Theory Problem

94 Troll Druid
6125
Posts: 138
Let G be a connected graph in which all vertices have even degree. Prove that G
has a cycle.
Reply Quote
.
Edited by Yuen#1344 on 8/14/2013 9:02 PM PDT
Reply Quote
Probably this?
http://www.proofwiki.org/wiki/Graph_with_Even_Vertices_Partitions_into_Cycles
Reply Quote
Someone is going to fail their exam.
Reply Quote
94 Troll Druid
6125
Posts: 138
I'm just trying to understand. This isn't due -- it's on a study guide. If you want to "poke fun" at me, go for it, it doesn't bother me.

Edit: Also, any help is appreciated. =)
Edited by Cursley#1886 on 3/5/2013 10:12 PM PST
Reply Quote
But why posting it here?

Then better:
Let E be a fire-chain-connected elite pack in which all demons have even damage. Prove that E has a legendary to drop.

Sorry, sounds like trolling. :) But I really wonder why here.
I gave you a link and hope that helps.
Edited by Forelle#1338 on 3/5/2013 10:22 PM PST
Reply Quote
Step 1: Suppose that G is connected and all vertices are even, and G doesn't have a cycle.

Step 2: ???

Step 3: Get a contradiction.
Edited by Prime#1988 on 3/5/2013 10:33 PM PST
Reply Quote
.
Edited by Yuen#1344 on 8/14/2013 9:03 PM PDT
Reply Quote
Pf: Suppose that G is connected and all vertices are even, and suppose that G doesn't have a cycle. This will yield a contradiction. Let P and Q be two vertices in G. Since G is connected, there is a path from P to Q, say, A_1 U A_2 U ... U A_{n-1} U A_n, where A_1 = P, A_n = G, and n is an positive integer. Moreover, since all vertices in G are even, there is at least one other path "going out" of Q=A_n (going out in the sense that the path from P to Q that traversed A_{n-1} was "going in," despite the fact that G is not a directed graph). Let A_k denote the vertice that we would arrive at if we "traveled out" of Q=A_n. But since G is connected, there exists a path from A_k to P. Therefore there exists a path from Q=A_n to P, that being, A_n U A_k U A_{i_1} U ... U A_{i_m} U A_1. But these two paths form a cycle. This contradicts our assumption that G doesn't have a cycle. Thus our initial assumption was wrong and hence every connected graph G has a cycle, provided that all it's vertices are even. This completes the proof.

Disclaimer: I have no idea what I'm doing. :P
Edited by Prime#1988 on 3/5/2013 10:49 PM PST
Reply Quote
.
Edited by Yuen#1344 on 8/14/2013 8:59 PM PDT
Reply Quote
94 Troll Druid
6125
Posts: 138
Pf: Suppose that G is connected and all vertices are even, and suppose that G doesn't have a cycle. This will yield a contradiction. Let P and Q be two vertices in G. Since G is connected, there is a path from P to Q, say, A_1 U A_2 U ... U A_{n-1} U A_n, where A_1 = P, A_n = G, and n is an positive integer. Moreover, since all vertices in G are even, there is at least one other path "going out" of Q=A_n (going out in the sense that the path from P to Q that traversed A_{n-1} was "going in," despite the fact that G is not a directed graph). Let A_k denote the vertice that we would arrive at if we "traveled out" of Q=A_n. But since G is connected, there exists a path from A_k to P. Therefore there exists a path from Q=A_n to P, that being, A_n U A_k U A_{i_1} U ... U A_{i_m} U A_1. But these two paths form a cycle. This contradicts our assumption that G doesn't have a cycle. Thus our initial assumption was wrong and hence every connected graph G has a cycle, provided that all it's vertices are even. This completes the proof.

Disclaimer: I have no idea what I'm doing. :P


I love contradictions.
Reply Quote

Please report any Code of Conduct violations, including:

Threats of violence. We take these seriously and will alert the proper authorities.

Posts containing personal information about other players. This includes physical addresses, e-mail addresses, phone numbers, and inappropriate photos and/or videos.

Harassing or discriminatory language. This will not be tolerated.

Forums Code of Conduct

Report Post # written by

Reason
Explain (256 characters max)

Reported!

[Close]