TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 14

14) Let G=(V, E) be a connected graph with an even number of vertices. Show that there is a (not necessarily connected) spanning subgraph (i.e. a subgraph with vertex set V) in which all vertices have odd degree. Is this also true for non-connected graphs?

Solution 1

https://web.archive.org/web/20180730233853/https://www.matheplanet.com/default3.html?call=viewtopic.php%3ftopic=173303&ref=https%253A%252F%252Fwww.google.at%252F

Solution 2

showing that this is true for trees is enough, as every connected graph has a tree as a subgraph.

Proof by induction on |V|

• for n=2 (starting with 2 because |V| must be even): OK
• now take an n>2 and even.
• let x be a vertex of the tree, which has leaves (xi={x1, x2, ..., xk}) as neighbours except one inner vertex x'
• let's have a closer look at x:
  • no x' exists i.e. all neighbours are leaves. k must be odd, d(xi)=1=odd and d(x)=k=odd. OK
  • x' exists:
    • k odd: edges from x to xi are kept in E, but the edge connecting x and x' are removed from E. Subgraph containing x and all xi: OK. Remaining Subgraph: do induction ("recursion") on it.
    • k even: edges x to xi and x to x' remain in E. Do induction on subgraph containing all vertices except the xi

Showing that it's not true for not connected graphs is easy: just find one example on which the statement does not hold, e.g. G=(V,E) : V={a,b} E={}