- #1
mss2718
- 2
- 0
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.
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.