prove : Let G be a graph that has exactly 2k vertices of odd degree. Show that(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph theory proof help needed

**Physics Forums | Science Articles, Homework Help, Discussion**