Indukcja matematyczna w twierdzeniu Eulera 1736

[Fray]

Witam

Mam problem ze zrozumieniem dowodu twierdzenia Eulera ( 1736 ), które głosi że:
Graf spójny \(\displaystyle{ G=(V,E)}\) ma cykl Eulera \(\displaystyle{ \Leftrightarrow \forall _{v \in V} 2 | deg(v)}\)

Rozumiem dowód w prawo, ale mam problemy z implikacją w lewo. Konkretnie nie rozumiem, co tu jest założeniem indukcyjnym.

Dla \(\displaystyle{ m=3}\) twierdzenie oczywiście zachodzi. Dla \(\displaystyle{ m>3}\) wiemy z odpowiedniego lematu, że graf zawiera jakiś cykl C. Jeżeli cykl zawiera cały graf, to dowód się kończy. Jeżeli nie to usuwamy go, dzieląc graf na spójne składowe.

I właśnie tutaj jest problem. Wszędzie jest napisane, że z założenia indukcyjnego wiemy iż każdy graf o ilości krawędzi \(\displaystyle{ n < m}\) ma cykl Eulera. Dlaczego? Jakie tu jest założenie i teza indukcyjna?

Pozdrawiam,
Fray

[Jytug]

Indukcja jest po liczbie krawędzi w grafie. Jeżeli są 3 krawędzie, to twierdzenie jest prawdziwe. Zakładamy więc, że dla każdego grafu, który ma mniej niż \(\displaystyle{ m}\) krawędzi implikacja zachodzi. Wykorzystujemy to założenie, rozbijając graf o \(\displaystyle{ m}\) krawędziach na takie, które spełniają założenie indukcyjne