Gráfelmélet. Hogyan mutassam meg, hogy egy tetszőleges páratlan hosszúságú zárt séta tartalmaz kört? Igaz-e ez páros hosszúságúra is?

Zárt séta vagy eleve kör, vagy van benne ismételt él vagy csúcs (az induló csúcsot leszámítva is). Vagyis pl. az A,B,C,D,A az egy kör, de az A,B,C,B,A nem kör, hanem csak zárt séta (az AB és BC élen illetve a B csúcson kétszer jártunk).

Páros hosszú zárt sétára, amiben NINCS kör, az A,B,C,B,A egy példa, hisz ez 4 hosszú (AB,BC,CB,BA). Szóval páros hosszúra nem igaz a tétel.

Páratlan hosszúakra teljes indukcióval:

- k=3 hosszú zárt séta az A,B,C,A, más 3 hosszú nem lehet. Ez maga egy kör, kész.

- Tegyük fel, hogy 2k−1-ig minden páratlan hosszúra teljesül, hogy van benne kör.

- Nézzük az n=2k+1 hosszúakat. A séta csúcsai V₁,V₂,...,Vn,V₁.

Ez vagy eleve kör (akkor kész vagyunk), vagy van benne egy Vi és Vj (i<j) páros, amik valójában ugyanazok a csúcsok.

Bontsuk két sétára az eredeti sétát: az egyik a V₁...Vi,Vj+1,...Vn,V₁ séta (vagyis kihagytuk belőle a Vᵢ...Vj szakaszt), a másik pedig pont ez a Vᵢ...Vj séta. Ez is séta, hisz Vj ugyanaz a csúcs, mint Vi.

Mindkét séta rövidebb az eredeti 2k+1 hosszúnál, és a két séta közül az egyik páros, a másik páratlan. A páratlanban az indukciós feltevés miatt van kör.

Kész.

Vedd észre, hogy a feladatnál többet is igazoltunk: azt, hogy tetszőleges páratlan hosszú zárt séta tartalmaz kört, ÉS EZ A KÖR PÁRATLAN HOSSZÚ.

|Megjegyzés: egyszerű gráfot feltételez a fenti gondolatmenet, de hurkokat vagy többszörös éleket tartalmazó gráfokra is ki lehet terjeszteni: olyankor a legegyszerűbb páratlan hosszú zárt séta a k=1 hosszú A,A séta, vagyis egy hurok. Ez maga egy kör is. A teljes indukciós bizonyítás folytatása változatlan.