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

Jump to navigation
Jump to search

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?

## Theory[edit | edit source]

## Solution 1[edit | edit source]

## Solution 2[edit | edit source]

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={}