Let G be a connected graph in which all vertices have even degree. Prove that G

has a cycle.

has a cycle.

Let G be a connected graph in which all vertices have even degree. Prove that G

has a cycle.

has a cycle.

.

Edited by Yuen#1344 on 8/14/2013 9:02 PM PDT

Probably this?

http://www.proofwiki.org/wiki/Graph_with_Even_Vertices_Partitions_into_Cycles

http://www.proofwiki.org/wiki/Graph_with_Even_Vertices_Partitions_into_Cycles

Someone is going to fail their exam.

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

Edit: Also, any help is appreciated. =)

Edited by Cursley#1886 on 3/5/2013 10:12 PM PST

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.

Then better:

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

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.

Step 2: ???

Step 3: Get a contradiction.

Edited by Prime#1988 on 3/5/2013 10:33 PM PST

.

Edited by Yuen#1344 on 8/14/2013 9:03 PM PDT

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

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

Edited by Prime#1988 on 3/5/2013 10:49 PM PST

.

Edited by Yuen#1344 on 8/14/2013 8:59 PM PDT

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.

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