Bonjour et meilleurs voeux pour cette année du bac.
Bon, regardons vos questions :
On considère un graphe non orienté connexe dont tous les sommets sont de degré pair.
Pourquoi est-il toujours possible de partir d'un sommet quelconque par une arrête et d'y revenir par une autre arrête ?
- Partons d'un sommet x0 et empruntons une arête qui lui est adjacente (il en existe car G est connexe).
- Marquons cette arête. (elle ne peut plus être empruntée).
- On arrive à un sommet x1.
- Le nombre d'arêtes marquées qui sont adjacentes à x1 est 1. Comme degré(x1) est pair, il existe une arête non encore marquée qui lui est adjacente. On l'emprunte.
- On avance tant qu'on n'est pas bloqué et tant qu'on n'est pas revenu sur x0.
Question : peut-on être bloqué sans être revenu sur x0 ?
Réponse : non.
Car, à un instant quelconque, supposons que l'on vienne d'arriver sur un sommet x et que l'on soit bloqué (c'est à dire que toutes les arêtes adjacentes à x ont déjà été marquées).
Si on note k le nombre de fois où l'on est passé par x avant d'y arriver et d'y être bloqué alors le nombre d'arêtes adjacentes à x qui ont été marquées est :
2*k+1
-> 2*k car à chaque fois que l'on traverse x, on marque l'arête par laquelle on est venu et celle par laquelle on repart.
-> +1 car on est arrivé sur x une dernière fois.
Donc cela signifierait que degré(x) = 2k+1.
Impossible ! car les degrés des sommets sont pairs.
Donc il est impossible d'être bloqué sur un sommet.
Conséquence : la méthode de parcours décrite au-dessus s'arrête lorsque on arrive sur x0.
En quoi le fait d'être connexe at-il son importance ?
Le seul intérêt que je vois pour la connexité de G est que l'on est sûr qu'aucun sommet à un degré égal à 0.
Car sinon, la première propriété serait fausse.
Construit-on aisi un cycle ?
Oui car un cycle est un chemin où les points de départ et d'arrivée sont les mêmes et où les arêtes sont distinctes.
Si on supprime les arrêtes parcourues au cours d'un cycle, que dire du dedré des sommets?
Pour chaque sommet x parcouru par le cycle, si on note k le nombre de fois où l'on est passé par x, alors il y aura 2*k arêtes marquées qui vont être supprimées (k entrantes et k sortantes).
Donc le degré de x après suppression des arêtes est diminué de 2*k. Comme initialement le degré est pair, il reste toujours pair.
Peut on alors partir d'un sommet déjà utilisé et construire un nouveau cycle à l'aide des arrêtes ?
Après suppression des arêtes, le graphe n'est plus forcément connexe, mais ses sommets ont toujours des degrés pairs.
Si on part d'un sommet de degré non nul, en appliquant la méthode de parcours décrite dans la première question, on est sûr de créer un nouveau cycle.