Példa: Séták, hegyek

Egy tó két oldalán egy-egy hegy van, amelyek magassága ugyanaz, továbbá mindkettőn egy-egy turista út vezet fel a tótól a csúcsig, amelyekre teljesülnek a következő feltételek:

  1. Az utak véges sok szakaszra bonthatók úgy, hogy a szakaszok a `fel' és `le ' kategóriák között váltakozzanak. A fel típusú szakaszon haladva a tó szintjéhez mért magasságunk szigorúan növekszik, míg egy le szakaszon haladva magasságunk szigorúan csökken. (Ha a tó felöl indulva haladunk előre, akkor egy fel szakasz kezdőpontját völgynek nevezzük. (Az egész út kezdőpontja egy völgy, az összes többi völgy olyan pont ahová egy le szakasz megtételével jutottunk.) Egy fel szakasz végpontját oromnak nevezzük. (A hegy csúcsa egy orom, a további ormok olyan pontok, ahonnan egy le szakasszal foltatódik az út.)
  2. Az utak sohasem süllyednek le a tó szintje alá. (A csúcs definíciójából pedig következik, hogy az utak nem emelkednek a csúcs fölé. Azaz a tó szintjének síkja és a hegyek csúcsainak vízszintes síkja egy sávot alakít ki, amelyen belül zajlik a példánk.)
A két hegy lábainál egy szerelmes pár áll. Az egyik oldalon a fiú, a másikon a lány. Az az ötletük támad, hogy mindketten megmásszák az előttük lévő hegyet úgy, hogy a mászás közben mindig ugyanolyan magasságban lesznek. Lássuk be, hogy megtehetik ezt.

A két hegyen egy-egy mászót, akik ugyanazon magasságban vannak konfigurációnak nevezzük. Legyen A az a konfiguráció, amikor mindkét mászó a tónal (a hegy lábánál) van. Legyen Z az a kofiguráció, amikor mindkét mászó a csúcson van. Ha egy konfiguráció valamelyik mászója völgyben vagy ormon van, akkor a konfigurációt extremálisnak nevezzük. A és Z is extremális konfigurációk. Két extremális konfiguráció szomszédos Ha egyikből a két mászó a másikba sétálhat úgy, hogy közben mindig közös magasságban legyenek és ne haladjanak át extremális konfiguráción. Ezzel egy egyszerű gráfot definiáltunk. A éz Z a két csúcs a gráfnak.

Egy mászás megfelel egy sétának a gráfban. Egy extremális konfigurációból (A-ból) indulunk és mindkét mászó elkezd emelkedni. Nem sokára egyikük egy oromra érkezik. (Eltekintünk attól a lehetőségtől, hogy a két emelkedő ``közepén'' megfodulnak (a közös magasságtartás miatt mindketten egyszerre) és visszatérnek a tóhoz. Az ilyen felesleges kitérőket kivágjuk a mászás folyamatából.) Így gráfunkban A-ból egy szomszédos csúcsba kerültünk. És így tovább. Eljárásunk megfordítható. Egy gráfbeli sétához tartozik egy mászás. Így feladatunk ekvivalens azzal, hogy belássuk, hogy gráfunkban van AZ-séta.

Persze célunkat máshogy is megfogalmazhatjuk: Be kell látnunk, hogy van AZ-út. Be kell látnunk, hogy A és Z gráfunk ugyanazon a komponensébe esik.

Vizsgáljuk meg gráfunk pontjainka fokait. Először az A és Z-től különböző csúcsokat vegyünk. Egy csúcs egy konfigurációnak felel meg, amely egyik mászója völgy vagy orom pozícióban van. A másik mászó lehet völgy vagy orom pozícióban, de lehet ezek egyikében sem. Ilyenkor azt mondjuk, hogy közönséges pozícióban van. Tehát egy extremális konfigurációhoz/ponthoz a gráfunkban hozzárendelhető egy típus, ami lehet v(ölgy)-v, v-o(rom), v-k(özönséges), o-o,o-k. A pont foka csak a típustól függ. A v-v pontok foka 4, a v-k pontok foka 2, a v-o pontok foka 0, az o-o pontok foka 4, az o-k pontok foka 2. Könnyű látni, hogy az A, illetve Z pontok foka 1. Tehát A és Z gráfunk pontosan két pontja, amleyek foka páratlan.

Ebből egyszerűen következik az állítás: Az A-ból induló mohó vonalnövelésnek Z-ben kell elakadni. Így adódik a bizonyítandó. Egy másik indoklás: A komponensében lennei kell A-tól különböző páratlan fokú pontnak. Ez csak Z lehet.