Euler-Touren

Ein zusammenhängender Graph $G$ hat genau dann eine Euler-Tour, wenn der Grad jedes Knotens gerade ist.

• Hinrichtung: Zeige: Wenn $G$ eine Euler-Tour hat, dann hat jeder Knoten in $G$ geraden Grad. Sei $(v_0,e_1,v_1,e_2,...,e_m,v_m=v_0)$ eine Euler-Tour.
  • Definiere $e_{m+1}=e_1$. Nach Definition einer Euler-Tour gilt $e_i\ne e_j$ für alle $1\le i\ne j\le m$. Weiterhin kommt jede Kante genau einmal in $\{e_1,...,e_m\}$ vor.
  • Für $u\in V(G)$ sei $I(u):=\{i\mid 1\le i\le m,v_i=u\}$. Dann gilt: $${e \in E(G) \mid u \text{ ist inzident zu } e} = {e_i, e_{i+1} \mid i \in I(u)}$$
  • Da $G$ keine Schleifen enthält und per Definition einer Euler-Tour $e_i\ne e_j$ für alle $1\le i\ne j\le m$, gilt $\{e_i,e_{i+1}\}\cap \{e_j,e_{j+1}\}=\mathrm{\varnothing }$ für alle $i\ne j\in I(u)$. Also ist $d_G(u)=2\cdot |\{i\mid i\in I(u)\}|$ und daher gerade.
• Rückrichtung: Zeige: Wenn der Grad jedes Knotens in $G$ gerade ist, dann hat $G$ eine Euler-Tour.
  • Behauptung 1: $G$ enthält einen geschlossenen Kantenzug, in dem keine Kante wiederholt wird.
    • Beweis: Wir konstruieren eine Folge $C_1,C_2,...$ von Kantenzügen, in denen keine Kante wiederholt wird, wie folgt: Wähle $e_1=\{v_0,v_1\}\in E(G)$ beliebig und definiere $C_1=(v_0,e_1,v_1)$.
      • Sei $C_i=(v_0,e_1,...,e_i,v_i)$ schon konstruiert.
      • Wenn $v_i$ zu einer noch nicht benutzten Kante $e=\{v_i,v^{\prime }\}$ inzident ist, definiere $C_{i+1}=(v_0,e_1,...,e_i,v_i,e,v^{\prime })$.
      • Ansonsten hört die Konstruktion hier auf.
    • Da jeder Knoten geraden Grad hat, können wir $C_i$ nur dann nicht erweitern, wenn $v_i=v_0$ ist und alle zu $v_i$ inzidenten Kanten schon durchlaufen wurden. Also ist $C_i$ in diesem Fall ein geschlossener Kantenzug.
  • Konstruktion der Tour (Verfahren): Wir konstruieren eine Folge von geschlossenen Kantenzügen $T_1,...$ in denen keine Kante wiederholt wird wie folgt: Wähle einen geschlossenen Kantenzug $T_1$ ohne Wiederholung einer Kante beliebig. Dies geht nach Behauptung 1.
    • Sei nun $T_i=(v_0,e_1,...,v_j,e_{j+1},v_{j+1},...,e_l,v_l=v_0)$ schon konstruiert.
      • Wenn $T_i$ alle Kanten aus $G$ enthält, ist $T_i$ eine Euler-Tour.
      • Ansonsten gibt es einen Knoten $v_j$ (für ein $1\le j\le l$) und eine Kante $f_1=\{v_j,u_1\}\in E(G)$, so dass $f_1\ne e_s$ für alle $1\le s\le l$.
    • Wie im Beweis von Behauptung 1 konstruieren wir einen geschlossenen Kantenzug $C=(v_j,f_1,u_1,...,f_k,v_k=v_j)$, in dem keine Kante wiederholt wird und der keine Kante aus $T_i$ benutzt. Dies geht, da in $G-\{e_1,...,e_l\}$ jeder Knoten geraden Grad hat.
  • Definiere $T_{i+1}=(v_0,e_1,...,v_j,f_1,u_1,...,f_k,v_k=v_j,e_{j+1},...,e_l,v_l=v_0)$. Da $G$ endlich ist, terminiert das Verfahren irgendwann mit einer Euler-Tour $T_i$.

Nach Behauptung 1 enthält $G$ einen geschlossenen Kantenzug, in dem keine Kante wiederholt wird. Sei $T$ ein solcher Kantenzug mit einer maximalen Anzahl an Kanten.

Behauptung: $T$ ist eine Euler-Tour.

Beweis: Sei $F$ die Menge der Kanten, die in $T$ vorkommen. Wenn $F\ne E(G)$, dann gibt es einen Knoten $v_j$ in $T$, der zu einer Kante $e\in E(G)\setminus F$ inzident ist. Dies gilt, da $G$ zusammenhängend ist. Nach Behauptung 1 gibt es in $G-F$ einen geschlossenen Kantenzug $C$, der $v_j$ und $e$ enthält und keine Kante wiederholt. Dann können wir $T$ durch $C$ erweitern, im Widerspruch dazu, dass $T$ kantenmaximal gewählt wurde.