Mixing
Prove that if a graph has exactly two vertices of odd degree, there must be a path joining these two vertices. [on hold]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Prove that if a graph has exactly two vertices of odd degree, there must
be a path joining these two vertices.
graph-theory
asked Aug 3 at 20:19
Dalveer Singh
61
put on hold as off-topic by amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger Aug 4 at 2:10
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger
 |Â
show 3 more comments
up vote
1
down vote
favorite
Prove that if a graph has exactly two vertices of odd degree, there must
be a path joining these two vertices.
graph-theory
asked Aug 3 at 20:19
Dalveer Singh
61
put on hold as off-topic by amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger Aug 4 at 2:10
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger
Corollary: All such graphs are connected.
– dan_fulea
Aug 3 at 20:21
2
This appears to be simply posting a homework problem, something frowned upon here. You would receive a more positive reaction if you were to show some effort to solve it.
– Acccumulation
Aug 3 at 20:22
1
@dan_fulea Nope. The two vertices of odd degree must be in the same component but that doesn't mean the graph is connected.
– bof
Aug 3 at 20:24
1
Start from one of the two vertices with odd degree. Since odd implies $>0$, then you can exit that vertex and go to another vertex. If you happened to fall in the other vertex of odd degree, then you are done. If not, delete the edge that you just used. The new vertex in which you are has now odd degree. Apply induction on the number of vertices.
– spiralstotheleft
Aug 3 at 20:27
@dan_fulea The complement of $K_2,3$ has exactly two vertices of odd degree but is not connected.
– bof
Aug 3 at 20:27
 |Â
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Prove that if a graph has exactly two vertices of odd degree, there must
be a path joining these two vertices.
graph-theory
asked Aug 3 at 20:19
Dalveer Singh
61
Prove that if a graph has exactly two vertices of odd degree, there must
be a path joining these two vertices.
graph-theory
asked Aug 3 at 20:19
Dalveer Singh
61
asked Aug 3 at 20:19
Dalveer Singh
61
asked Aug 3 at 20:19
Dalveer Singh
61
asked Aug 3 at 20:19
Dalveer Singh
61
61
put on hold as off-topic by amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger Aug 4 at 2:10
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger
put on hold as off-topic by amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger Aug 4 at 2:10
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Especially Lime, Math1000, Shailesh, Bob Krueger
Corollary: All such graphs are connected.
– dan_fulea
Aug 3 at 20:21
2
This appears to be simply posting a homework problem, something frowned upon here. You would receive a more positive reaction if you were to show some effort to solve it.
– Acccumulation
Aug 3 at 20:22
1
@dan_fulea Nope. The two vertices of odd degree must be in the same component but that doesn't mean the graph is connected.
– bof
Aug 3 at 20:24
1
Start from one of the two vertices with odd degree. Since odd implies $>0$, then you can exit that vertex and go to another vertex. If you happened to fall in the other vertex of odd degree, then you are done. If not, delete the edge that you just used. The new vertex in which you are has now odd degree. Apply induction on the number of vertices.
– spiralstotheleft
Aug 3 at 20:27
@dan_fulea The complement of $K_2,3$ has exactly two vertices of odd degree but is not connected.
– bof
Aug 3 at 20:27
 |Â
show 3 more comments
Corollary: All such graphs are connected.
– dan_fulea
Aug 3 at 20:21
2
This appears to be simply posting a homework problem, something frowned upon here. You would receive a more positive reaction if you were to show some effort to solve it.
– Acccumulation
Aug 3 at 20:22
1
@dan_fulea Nope. The two vertices of odd degree must be in the same component but that doesn't mean the graph is connected.
– bof
Aug 3 at 20:24
1
Start from one of the two vertices with odd degree. Since odd implies $>0$, then you can exit that vertex and go to another vertex. If you happened to fall in the other vertex of odd degree, then you are done. If not, delete the edge that you just used. The new vertex in which you are has now odd degree. Apply induction on the number of vertices.
– spiralstotheleft
Aug 3 at 20:27
@dan_fulea The complement of $K_2,3$ has exactly two vertices of odd degree but is not connected.
– bof
Aug 3 at 20:27
Corollary: All such graphs are connected.
– dan_fulea
Aug 3 at 20:21
Corollary: All such graphs are connected.
– dan_fulea
Aug 3 at 20:21
2
2
This appears to be simply posting a homework problem, something frowned upon here. You would receive a more positive reaction if you were to show some effort to solve it.
– Acccumulation
Aug 3 at 20:22
This appears to be simply posting a homework problem, something frowned upon here. You would receive a more positive reaction if you were to show some effort to solve it.
– Acccumulation
Aug 3 at 20:22
1
1
@dan_fulea Nope. The two vertices of odd degree must be in the same component but that doesn't mean the graph is connected.
– bof
Aug 3 at 20:24
@dan_fulea Nope. The two vertices of odd degree must be in the same component but that doesn't mean the graph is connected.
– bof
Aug 3 at 20:24
1
1
Start from one of the two vertices with odd degree. Since odd implies $>0$, then you can exit that vertex and go to another vertex. If you happened to fall in the other vertex of odd degree, then you are done. If not, delete the edge that you just used. The new vertex in which you are has now odd degree. Apply induction on the number of vertices.
– spiralstotheleft
Aug 3 at 20:27
Start from one of the two vertices with odd degree. Since odd implies $>0$, then you can exit that vertex and go to another vertex. If you happened to fall in the other vertex of odd degree, then you are done. If not, delete the edge that you just used. The new vertex in which you are has now odd degree. Apply induction on the number of vertices.
– spiralstotheleft
Aug 3 at 20:27
@dan_fulea The complement of $K_2,3$ has exactly two vertices of odd degree but is not connected.
– bof
Aug 3 at 20:27
@dan_fulea The complement of $K_2,3$ has exactly two vertices of odd degree but is not connected.
– bof
Aug 3 at 20:27
 |Â
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Corollary: All such graphs are connected.
– dan_fulea
Aug 3 at 20:21
2
This appears to be simply posting a homework problem, something frowned upon here. You would receive a more positive reaction if you were to show some effort to solve it.
– Acccumulation
Aug 3 at 20:22
1
@dan_fulea Nope. The two vertices of odd degree must be in the same component but that doesn't mean the graph is connected.
– bof
Aug 3 at 20:24
1
Start from one of the two vertices with odd degree. Since odd implies $>0$, then you can exit that vertex and go to another vertex. If you happened to fall in the other vertex of odd degree, then you are done. If not, delete the edge that you just used. The new vertex in which you are has now odd degree. Apply induction on the number of vertices.
– spiralstotheleft
Aug 3 at 20:27
@dan_fulea The complement of $K_2,3$ has exactly two vertices of odd degree but is not connected.
– bof
Aug 3 at 20:27