Problème — Regrouper par arbre couvrant

1. La preuve, en deux temps. Soit $T$ un arbre couvrant minimal du graphe complet des distances, et soit $\mathcal{C}$ la répartition obtenue en retirant de $T$ ses $k-1$ arêtes les plus lourdes — elle a bien $k$ groupes, puisque retirer une arête d'un arbre le coupe en deux. Notons $d^{\ast }$ le poids de la plus légère des arêtes retirées.

Premier temps : l'espacement de $\mathcal{C}$ vaut exactement $d^{\ast }$. Il est $\le d^{\ast }$, puisque l'arête retirée de poids $d^{\ast }$ joint deux points de groupes différents. Pour l'autre sens, on raisonne sur l'exécution de Kruskal, qui construit $T$ en prenant les arêtes par poids croissant : $\mathcal{C}$ est l'état de la structure unir & trouver au moment où il ne reste que $k$ classes, et toutes les arêtes prises jusque-là pèsent $\le d^{\ast }$. Supposons deux points $p$ et $q$ de groupes différents avec $d(p,q)<d^{\ast }$. Kruskal aurait examiné $\{p,q\}$ avant d'atteindre $d^{\ast }$, donc à un instant où $p$ et $q$ étaient déjà dans des classes distinctes — les classes ne font que fusionner. Il l'aurait donc prise, et $p$ et $q$ se retrouveraient dans le même groupe. Contradiction.

Second temps : aucune répartition ne fait mieux. Soit ${\mathcal{C}}^{\prime }$ une autre répartition en $k$ groupes. Comme ${\mathcal{C}}^{\prime }\ne \mathcal{C}$ et que les deux ont $k$ groupes, il existe deux points $p$ et $q$ dans le même groupe de $\mathcal{C}$ et dans deux groupes différents de ${\mathcal{C}}^{\prime }$. Le chemin de $p$ à $q$ dans $T$ reste entièrement dans un groupe de $\mathcal{C}$, donc toutes ses arêtes pèsent $\le d^{\ast }$. Ce chemin part d'un groupe de ${\mathcal{C}}^{\prime }$ et arrive dans un autre : il contient donc une arête $\{a,b\}$ dont les extrémités sont dans deux groupes différents de ${\mathcal{C}}^{\prime }$. L'espacement de ${\mathcal{C}}^{\prime }$ est majoré par le poids de cette arête, donc par $d^{\ast }$.