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

share|cite|improve this question

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

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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

Prove that if a graph has exactly two vertices of odd degree, there must
be a path joining these two vertices.

graph-theory

share|cite|improve this question

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

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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

share|cite|improve this question

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

share|cite|improve this question

asked Aug 3 at 20:19

Dalveer Singh

61

share|cite|improve this question

share|cite|improve this question

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

If this question can be reworded to fit the rules in the help center, please edit the question.

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

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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