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

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