Lanț - Grafuri neorientate

Lungimea unui lanț este numărul de muchii pe care acesta îl conține (sau numărul de noduri $-1$).

Lanțurile în graful neorientat pot fi clasificate după mai multe criterii.

În funcție de muchii:

• lanț simplu : toate muchiile din lanț sunt diferite între ele (nu se repetă nicio muchie);
• lanț compus : se pot repeta unele muchii de mai multe ori.

În funcție de noduri:

• lanț elementar : toate nodurile diferă 2 câte 2 (nu se trece prin același nod de 2 ori);
• lanț neelementar : se pot repeta nodurile (se poate trece prin același nod de 2 ori).

Exemple de lanțuri în graful neorientat:

Toate lanțurile din exemplu sunt lanțuri simple. De asemenea:

• L1 este lanț elementar de lungime 2;
• L2 este lanț elementar de lungime 4 (toate nodurile diferă);
• L3 este lanț elementar de lungime 6 (cel mai lung lanț elementar posibil, $n-1$ muchii);
• L4 este lanț neelementar de lungime 4 (se repetă nodul 5);
• L5 este lanț neelementar de lungime 9.

Dacă găsim un lanț între două noduri $x$ și $y$, atunci putem găsi și un lanț elementar între $x$ și $y$.

Un exemplu pentru această teoremă demonstrează foarte ușor teorema.

Putem evita „bucla” formată din nodurile $3$ și $2$, iar astfel obținem un lanț elementar.

Deducția teoremei apare și din definiția lanțului neelementar. Deoarece se trece de două ori printr-un nod, apare ceea ce numim un subciclu, care poate fi evitat.