Cycle graphe

[Toto256]

Bonjour,

Voici une question que j'ai du mal à traiter : on souhaite prouver le théorème de Dirac sur les graphes : Soit G un graphe fini simple connexe non orienté à n sommets. On suppose que tous les sommets ont degré au moins n/2. Alors G est hamiltonien.
A un moment de la preuve, on suppose que l'on puisse construire un cycle de longueur k + 1 sans répétition de sommets, dont les sommets sont notés a_0, · · · , a_k. Il faut montrer que k = n-1. On a déjà montré plus haut que k <= n+1.
Je pense supposer par l'absurde k < n-1. Le cycle contient k+1 sommets et k+1 <n. Cela veut dire que on peut trouver un sommet v du graphe qui n'est pas dans le cycle avec deg(v) >= n/2. C'est là que j en'arrive plus à avancer. Merci d'avance.

[Toto256]

Je pense avoir résolu le problème, on suppose k < n-1 donc k+1 < n. On dispose donc d'un sommet y du graphe qui n'est pas dans le cycle. Mais alors par connexité du graphe, il existe un indice l et un chemin liant y et a_l. Mais le chemin obtenu est plus grand que le chemin maximal généré par le cycle, ce qui est impossible. Donc k>= n-1, et comme on avait précédemment montré k<= n-1, on a k = n-1.