1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Check this

  1. Mar 21, 2007 #1
    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

    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.
  2. jcsd
  3. Mar 22, 2007 #2
    sound ok to me...
  4. Mar 22, 2007 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook