Définition
On appelle :
- Chaîne : une liste ordonnée d’arêtes permettant de décrire un « chemin » reliant un sommet à un autre.
- Longueur d’une chaîne : le nombre d’arêtes composant la chaîne.
- Chaîne fermée : une chaîne dans laquelle le sommet de depard est le même que celui d’arrivé.
- Chaîne ouverte : une chaîne non fermée (sommets de depard et d’arrivé distincts).
- Cycle : une chaîne fermée constituée d’arêtes toutes distinctes.
- Chaîne eulérienne : une chaîne qui contient une fois et une seule fois chaque arêtes du graphe.
- Cycle eulérien : une chaîne eulérienne fermée.
- Graphe connexe : un graphe dans lequel il n’y a pas de sommets isolés.
Propriété
Un graphe connexe admet un cycle eulérien si et seulement si tous ces degrès sont pairs.
Un graphe connexe admet une chaîne eulérienne si et seulement si elle a uniquement deux sommets impairs (sommets de degrès impairs).
Définition
On appelle :
- Distance entre deux sommets : la plus courte longueur de chaîne qui les relient.
- Diamètre d’un graphe : la plus grande des distances entre deux de ces sommets.
Propriété
Pour tout entier 
Si 
est la matrice associée à un graphe alors le terme de 
situé à la 
ligne et à la 
colonne est égal au nombre de chaînes de longueur 
reliant le sommet 
à celui 
.
ces entre deux de ces sommets.
