Théorème de Graham-Pollak

Une partition en exactement ${\displaystyle n-1}$ graphes bipartis complets est facile à obtenir : il suffit d'ordonner les sommets et, pour chaque sommet à l'exception du dernier, de former un graphe étoile le reliant à tous les sommets supérieurs dans l'ordre[1]. D'autres partitions sont également possibles.

La preuve du théorème de Graham-Pollak décrite par Aigner & Ziegler[1]^,[9] (qui suivent Tverberg 1982) définit une variable réelle ${\displaystyle x_{i}}$ pour chaque sommet ${\displaystyle v_{i}\in V}$, où ${\displaystyle V}$ désigne l'ensemble des sommets du graphe. Notons ${\displaystyle L_{k}}$ et ${\displaystyle R_{k}}$ les sommets des côtés gauche et droit du ${\displaystyle k}$-ième graphe biparti, et notons ${\displaystyle X(S)}$, pour tout ensemble ${\displaystyle S}$ des sommets, la somme des variables pour les sommets ${\displaystyle S}$ :

${\displaystyle X(S)=\sum _{v_{i}\in S}x_{i}}$.

Avec ces notations, le fait que les graphes bipartis partitionnent les arêtes du graphe complet peut être exprimé par l'équation :

${\displaystyle \sum _{i<j}x_{i}x_{j}=\sum _{k}X(L_{k})X(R_{k})}$.

Considérons maintenant le système d'équations linéaires qui donne ${\displaystyle X(S)=0}$ et ${\displaystyle X(L_{k})=0}$ pour chaque ${\displaystyle k}$. Toute solution à ce système d'équations vérifie également les équations non linéaires :

${\displaystyle {\begin{aligned}0&=X(S)^{2}={\Bigl (}\sum _{i}x_{i}{\Bigr )}^{2}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{i<k}x_{i}x_{j}{\Bigr )}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{k}X(L_{k})X(R_{k}){\Bigr )}\\&=\sum _{i}x_{i}^{2}.\\\end{aligned}}}$.

Maintenant, une somme de carrés de variables réelles ne peut être nulle que si les variables sont toutes nulles : la solution triviale au système d'équations linéaires. S'il y avait moins de ${\displaystyle n-1}$ graphes bipartis complets, le système d'équations aurait moins de ${\displaystyle n}$ équations en ${\displaystyle n}$ inconnues et il aurait une solution non triviale, une contradiction. Le nombre de graphes bipartis complets doit donc être au moins ${\displaystyle n-1}$[1]^,[4].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graham–Pollak theorem » (voir la liste des auteurs).

• Dimension bipartie
• Couverture par sous-graphes bipartis complets

• Portail des mathématiques
• Portail de l'informatique théorique