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: 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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook