Lanț

  Fie G=(X,U) un graf neorientat.

Se numește lanț în graful neorientat G o succesiune de vârfuri.

Clasificarea lanțurilor

    1. În funcție de muchii:
  • simple: toate muchiile din lanț sunt diferite între ele (nu se repetă nicio muchie);
  • compuse: se pot repeta unele muchii de mai multe ori.
    2. În funcție de noduri:
  • elementare: toate nodurile diferă 2 câte 2 (nu se trece prin același nod de 2 ori);
  • neelementare: se pot repeta nodurile.
Graf neorientat lanțuri

Lungimea unui lanț reprezintă numărul de muchii pe care acesta îl conține.
  Spre exemplu, în figura anterioară, lanțul L3 este cel mai lung lanț elementar din graf, de lungime 6 (6 muchii în componența lui).

Teoremă

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

Explicația teoremei apare din faptul că într-un lanț presupus neelementar, un nod se repetă. Astfel, apare ca un fel de buclă (un Ciclul este un lanț în care primul nod coincide cu ultimul.subciclu), pe care dacă am ignora-o, am obține un lanț elementar.