• Support PF! Buy your school textbooks, materials and every day products Here!

Check this

  • Thread starter hyderman
  • Start date
  • #1
30
0
please help me with this question

Show that in every simple graph there is a path from any vertex of odd
degree to some other vertex of odd degree?

here is my answer please check and correct if its wrong thanx

ANSWER:
In a simple graph, the sum of the degrees of the vertices must always be even. Thus, if there is a vertex of odd degree, there must be another vertex of odd degree (so the sum will be even). If the graph is connected, then there is a path from any vertex to any other vertex. If it is not connected, it must be made up of connected subgraphs, and the sum of the degrees of the vertices of each connceted subgraph still has to be even – so the odd vertices in each connected subgraph must still come in pairs.
 

Answers and Replies

  • #2
47
0
sound ok to me...
 
  • #3
1,357
0
I think the "question" is badly phrased. For example, consider the graph consisting of one vertex. In this graph, there are no paths and no vertices of odd degree. The statement to prove should be this: Let G be a simple graph and v a vertex in G. If v has odd degree, then there is a path from v to u where u is a vertex of odd degree. You can prove this using contradiction and the fact that the sum of the degrees of all the vertices is even which you used in the first post.
 

Related Threads on Check this

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
860
Replies
3
Views
1K
Replies
3
Views
1K
Replies
5
Views
2K
Replies
2
Views
2K
Replies
5
Views
854
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
6
Views
600
Top