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