# Graph theory proof help needed

1. Oct 26, 2008

### mss2718

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. Oct 26, 2008

### mss2718

can anyone help