Introduction à la théorie des graphes/Exercices/Graphes et sous-graphes
Cycles
modifier1. 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.