1. Not finding help here? Sign up for a free 30min 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!

Graph theory proof help needed

  1. Oct 26, 2008 #1
    prove : Let G be a graph that has exactly 2k vertices of odd degree. Show that
    there are k edge-disjoint paths each of which joins a different pair of ver-
    tices of odd degree.

    I have to prove this with induction on k. There is a hint that I need to strenghten my induction hypothosis but I do not know what to strengthen it to. This is what i have tried so far:

    Base: with 2 vertices of odd degree, we can use a theorem already proved, that states that an eularien path exists if a graph has 2 vertcies of odd degree.

    Inductive step: Let G be a graph with 2(k+1) odd vertices, if we add an edge between any 2 of the odd vertices they become even and we get a graph with (2k) odd vertices. I can use my IH to conclude that this graph has k edge-disjoint paths...

    The problem is that when I take away this edge i have no way of saying conclusivly that I did not destroy one of those paths beccause I am taking away an edge not adding one in. Any help would be much appreciated.
  2. jcsd
  3. Oct 26, 2008 #2
    can anyone help
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Graph theory proof help needed