Graphe non orienté : définition (Maths expertes)

Un graphe non orienté est la donnée d'un ensemble fini de points, les sommets, et d'un ensemble de segments reliant certains de ces sommets, les arêtes. On considère ici des graphes où deux sommets sont reliés par au plus une arête.

• L'ordre du graphe est son nombre de sommets.
• Deux sommets reliés par une arête sont adjacents.
• Le degré d'un sommet est le nombre d'arêtes dont il est une extrémité.