De ce contează?
Ai văzut puzzle-ul „desenează plicul fără să ridici creionul de pe hârtie și fără să treci de două ori pe aceeași linie"? Unele figuri ies dintr-o singură trăsătură, altele te lasă mereu cu o linie nedesenată, oricât ai încerca. Surpriza e că nu ține de noroc: se poate citi dinainte, doar uitându-te la câte linii se întâlnesc în fiecare colț. Asta e exact ideea unui parcurs eulerian.
Intuiția
Un parcurs eulerian trece prin fiecare muchie exact o dată. Imaginează un nod ca pe un colț al desenului: de fiecare dată când intri în el pe o linie, trebuie să ieși pe alta. Liniile se consumă în perechi (una de intrare, una de ieșire). Dacă un colț are un număr par de linii, perechile se închid perfect. Dacă are un număr impar, rămâne o linie nepereche — și acolo ești obligat ori să pornești, ori să termini desenul.
Numărul de linii care ies dintr-un nod se numește grad. Nodurile de grad
impar sunt singurele în care o linie rămâne fără pereche — deci singurele
locuri unde traseul se poate bloca: capetele. De aici toată teorema: 0
noduri impare → ciclu (startul e liber, finalul e tot startul), exact 2 →
lanț (ele sunt obligatoriu capetele), 4 sau mai multe → imposibil,
pentru că un singur traseu nu are decât 2 capete.