↵ pour ouvrir · ↑↓ pour naviguer · Esc pour fermer
Source : Cayley, 1889
Un arbre est un graphe connexe sans cycle. Une forêt est un graphe sans cycle (pas nécessairement connexe).
1. Par récurrence : n=1 → 0 arête ✓. Pour n+1 sommets : un arbre sur n+1 sommets possède une feuille v (degré 1). En supprimant v et son arête, on obtient un arbre sur n sommets avec n−1 arêtes. L'arbre initial a donc (n−1)+1 = n arêtes. ✓
2. Σ degrés = 2(n−1) (car n−1 arêtes). Si tous les degrés étaient ≥ 2, la somme serait ≥ 2n > 2(n−1) — contradiction. Donc au moins un sommet de degré 1 (feuille). Enlever cette feuille → arbre sur n−1 sommets → autre feuille → au moins 2 feuilles au total. ✓
3. Connexe → il existe un chemin. Sans cycle → s'il en existait deux distincts (u→v par p₁ et p₂), leur union formerait un cycle — contradiction. Donc chemin unique. ✓
4. K₄ : n=4, formule de Cayley → τ(K₄) = 4⁴⁻² = 4² = 16 arbres couvrants. On peut vérifier en les listant par leurs degrés : les 16 arbres étiquetés sur 4 sommets.