Introduction à la théorie des graphes/Exercices/Graphes et sous-graphes

**Graphes et sous-graphes**
Leçon : Introduction à la théorie des graphes

Exercices n^o1
Chapitre du cours :	Graphes et sous-graphes
Exercices de niveau 16.
Exo préc. :	Sommaire

En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Graphes et sous-graphes
Introduction à la théorie des graphes/Exercices/Graphes et sous-graphes », n'a pu être restituée correctement ci-dessus.

Cycles

1. Trouver un exemple de cycle qui n’est pas 2-régulier.

Solution

1. Tout cycle passant deux fois par le même sommet n’est pas 2-régulier. Ainsi le graphe G=(V,E) défini par V={1,2,3,4,5} et E={ {1,2}{2,3}{3,4}{4,5}{5,3}{3,1} } est un cycle (le cycle 1 2 3 4 5 1) mais n’est pas 2-régulier, en effet d(3)=4.

Introduction à la théorie des graphes

Sommaire