die   Hydra   keinen   Ast   reproduzieren,   der   länger   als   derjenige   ist,   der   von   Herkules durchschlagen wurde. Damit könnte Herkules die Höhe der Hydra nicht mehr reduzieren und somit nicht mehr verkleinern. Die Hydra könnte nicht mehr besiegt werden. Unter Ausschluss dieser beiden Fälle wird sich die Höhe der Hydra mit Fortschreiten des Experimentes verringern. Beweis: Beweis mittels Induktion Für den Beweis werden zunächst drei weitere Bezeichner benötigt. - Sei h die Höhe der höchsten Ebene des Graphen. - Nun  betrachten  wir  die  Knoten  auf  der  zweithöchsten  Ebene.  Sei  g der höchste Ausgangsgrad, den ein beliebiger Knoten der zweithöchsten  Ebene  hat.  Dies  bedeutet,  dass  ein  Knoten  der  (h- 1)sten  Ebene  mit  maximal  g  Knoten  der  höchsten  Ebene  verbunden ist. Dabei ist g beschränkt, da der Ausgangsgrad aller Knoten < oo  ist. - Weiterhin sei k die Anzahl der Knoten auf der zweit höchsten Ebene, die   den   Ausgangsgrad   g   haben.   Sei   K   die   Menge   der   Knoten   der zweithöchsten Ebene mit dem Ausgangsgrad g. Da    die    sich    reproduzierenden    Teilgraphen    Kopien    des    betroffenen Segments   oberhalb   des   Fixknotens   k   sind,   kann   sich   h   niemals   erhöhen,   die   neuen Teilgraphen haben maximal die Höhe h. Ähnliches gilt für den maximalen Ausgangsgrad g der Knoten auf der (h-1)sten Ebene. Die Hydra reproduziert sich immer unterhalb der betroffenen Ebene. Die höchste betroffene Ebene ist maximal die Ebene (h-1), d.h. die Hydra kann sich maximal in einem Knoten der Ebene (h-2) reproduzieren. Aus diesem Grund kann sich, egal wie Herkules vorgeht, der maximale  Ausgangsgrad  g  nicht  vergrößern,  es  entstehen  nur  auf  der  (h-1)sten  Ebene weitere Kopien von bereits vorhandenen Knoten. Die Anzahl k der Knoten auf der (h-1)sten Ebene mit dem Ausgangsgrad g kann sich auch nicht   erhöhen.   Durchtrennt   Herkules   eine   Kante,   die   nicht   von   einem   Knoten   aus   K ausgeht, so enthält der neue Teilbaum auch keine Kopie eines Knotens aus K. Durchtrennt Herkules eine Kante eines Knotens f aus K, so ist dieser Knoten f nicht mehr in K, da dieser jetzt den Ausgangsgrad (g-1) hat. Weiterhin ist der reproduzierte Knoten f' des  reproduzierten  Teilbaums  nicht  in  K,  da  die  Reproduktion  nach  dem  Durchtrennen erfolgt und f' somit den Ausgangsgrad (g-1) hat. Da die Zahl der Knoten beschränkt ist, gibt es nur endlich viele Knoten in K. Durchtrennt Herkules  nacheinander  eine  Kante  eines  Knotens  aus  K,  so  reduziert  sich  k  mit  jedem Schlag um eins. Somit ist k nach endlich vielen Schritten 0. Ist dies der Fall reduziert sich g zu g', da es keinen Knoten mehr mit dem Ausgangsgrad g gibt. Damit reduziert sich g zu g' mindestens um Eins. Die Menge K besteht nun wieder aus k' Knoten, alle Knoten der (h- 1)sten Ebene mit Ausgangsgrad g'. Wiederholt man diese Prozedur, so verringert sich auch g zu g' < g zu g'' < g' usw. Dies kann solange  wiederholt  werden,  bis  g*  =  0.  Ist  der  maximale  Ausgangsgrad  der  Knoten  der zweit höchsten Ebene = 0, so besteht die höchste Ebene aus keinem Knoten, die Höhe des Graphen hat sich um eins reduziert. Nun wird h, g, k und K neu gesetzt, die Prozedur beginnt von neuem, bis die maximale Höhe des Graphen auf eins reduziert ist. In diesem Fall kann sich die Hydra nicht mehr reproduzieren, die restlichen Äste können von Herkules durchtrennt werden. Es  ist  nicht  notwendig,  dass  Herkules  mit  Knoten  aus  K  beginnt.  Durchtrennt  er  zuerst ausgehende Kanten von Knoten, die nicht aus K sind, so erhöht sich weder h, noch k, noch g.  Es  bleibt  nur  zu  zeigen,  dass  Herkules  Kanten  von  Knoten  aus  K  nach  endlicher  Zeit durchtrennen muss. Dies    kann    man    sich    leicht    überlegen.    Unter    der    Annahme,    dass    Herkules    keine ausgehenden Kanten von Knoten aus K durchtrennt kann man annehmen, dass die zu den Knoten  aus  K  führenden  und  aus  K  herausführenden  gesamten  Teilgraphen  für  Herkules und  die  Hydra  "gesperrt"  sind.  Herkules  durchtrennt  diese  Kanten  nicht  und  damit  kann die Hydra diese Teilgraphen nicht reproduzieren. Damit lässt sich wieder ein h, g, k und K finden  für  alle  Knoten,  die  nicht  "gesperrt"  sind.  Hier  lässt  sich  das  oben  beschriebene Prinzip erneut durchführen, weiterhin lassen sich auch diese Teilgraphen "sperren", bis ein … … … n Köpfe Abbildung 2.2