Version Bêta · Lancement officiel le 28 août 2026 Signaler un bug

Circuit hamiltonien et graphe complet

Difficile Inspiré BAC France
Partager
Exercice inspiré d'un BAC France
Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

On considère le graphe complet à 5 sommets .

  1. Donner le nombre d'arêtes de et le degré commun de chaque sommet.
  2. Justifier que admet un cycle eulérien.
  3. Montrer qu'un circuit hamiltonien existe dans et en exhiber un.
  4. Combien existe-t-il de circuits hamiltoniens distincts dans ?

Indices

— clique pour révéler
1 Indice 1
Pour compter les aretes d'un graphe complet a $n$ sommets, pense au nombre de paires de sommets possibles : c'est une combinaison $\\binom{n}{2}$.
2 Indice 2
Pour le cycle eulerien, rappelle-toi le theoreme d'Euler : un graphe connexe admet un cycle eulerien si et seulement si tous ses sommets ont un degre pair. Verifie la parite du degre commun trouve a la question 1.
3 Indice 3
Pour le circuit hamiltonien, essaie de visiter chaque sommet une seule fois puis de revenir au depart ; pour compter le nombre total de circuits distincts, pense au nombre de facons d'ordonner les sommets restants une fois le point de depart fixe, en tenant compte du sens de parcours.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Chemin de longueur $k$ et interprétation combinatoire Retour au chapitre Circuit hamiltonien sur un graphe complet $K_4$