Graphe chemin

En théorie des graphes, un graphe chemin ou graphe chaîne (en anglais path graph) est un arbre où chaque nœud est de degré au plus deux.

Graphe chemin
Graphe chemin à 6 sommets
Nombre de sommets	$n$
Nombre d'arêtes	$n-1$
Rayon	$\lfloor n/2\rfloor$
Diamètre	$n-1$
Automorphismes	2
Nombre chromatique	2
Indice chromatique	2
Propriétés	distance-unité

Voir aussi

• Chemin
• Chaîne
• Graphe cycle, le seul autre type de graphe connexe dont tous les sommets sont de degré au plus deux.
• Graphe chenille