# Théorème de Graham-Pollak

En théorie des graphes, le théorème de Graham-Pollak affirme que les arêtes d'un graphe complet à $n$ sommets ne peut être partitionné en moins de $n-1$ graphes bipartis complets. Il a d'abord été publié par Ronald Graham et Henry O. Pollak dans deux articles en 1971 et 1972, dans le cadre d'une application aux circuits de commutation téléphonique$^,$.
Le théorème est depuis devenu bien connu et a été étudié et généralisé à plusieurs reprises en théorie des graphes, en partie à cause de sa preuve élégante utilisant des techniques de la théorie algébrique des graphes$^,$$^,$$^,$$^,$. Plus précisément, Aigner & Ziegler écrivent que toutes les preuves sont basées d'une manière ou d'une autre sur l'algèbre linéaire : « aucune preuve combinatoire pour ce résultat n'est connue ».

## Construction d'une partition optimale

Une partition en exactement $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. D'autres partitions sont également possibles.

## Preuve de l'optimalité

La preuve du théorème de Graham-Pollak décrite par Aigner & Ziegler$^,$ (qui suivent Tverberg 1982) définit une variable réelle $x_{i}$ pour chaque sommet $v_{i}\in V$, où $V$ désigne l'ensemble des sommets du graphe. Notons $L_{k}$ et $R_{k}$ les sommets des côtés gauche et droit du $k$-ième graphe biparti, et notons $X(S)$, pour tout ensemble $S$ des sommets, la somme des variables pour les sommets $S$ :
    $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 :
    $\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 $X(S)=0$ et $X(L_{k})=0$ pour chaque $k$. Toute solution à ce système d'équations vérifie également les équations non linéaires :
    ${\begin{aligned}0&=X(S)^{2}={\Bigl\sum _{i}x_{i}{\Bigr )}^{2}\\&={\Bigl\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl2\sum _{i<k}x_{i}x_{j}{\Bigr )}\\&={\Bigl\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl2\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 $n-1$ graphes bipartis complets, le système d'équations aurait moins de $n$ équations en $n$ inconnues et il aurait une solution non triviale, une contradiction. Le nombre de graphes bipartis complets doit donc être au moins $n-1$$^,$.

## Problèmes liés
### Étiquetage en distances

Graham et Pollak étudient un problème d'étiquetage de graphes plus général, dans lequel les sommets d'un graphe sont étiquetés avec des chaînes de même longueur composées caractères "0", "1" et "✶", de telle sorte que la distance entre deux sommets quelconques est le nombre des positions des chaînes où un sommet est étiqueté avec un 0 et l'autre est étiqueté avec un 1. Un tel étiquetage, sans le caractère "✶", donne un plongement isométrique dans un hypercube, ce qui n'est possible que pour les graphes qui sont des cubes partiels, et dans l'un de leurs articles, Graham et Pollak appellent un étiquetage qui autorise des caractères "✶" un plongement dans un « cube écrasé ».
Pour chaque position des chaînes étiquettes, on peut définir un graphe biparti complet dans lequel un côté de la bipartition se compose des sommets étiquetés avec 0 dans cette position et l'autre côté se compose des sommets étiquetés avec 1, en omettant les sommets étiquetés "✶". Pour le graphe complet, deux sommets sont à distance un l'un de l'autre, donc chaque arête doit appartenir à exactement l'un de ces graphes complets. Ainsi, un tel étiquetage pour le graphe complet correspond à une partition de ses arêtes en graphes bipartis complets, avec les longueurs des étiquettes correspondant au nombre de graphes dans la partition.

### Conjecture d'Alon–Saks–Seymour

Noga Alon, Michael Saks et Paul Seymour ont formulé une conjecture au début des années 1990 qui, si elle est vérifiée, fournirait une généralisation substantielle du théorème de Graham–Pollak : ils ont conjecturé que toute partition des arêtes d'un graphe de nombre chromatique $k+1$ en sous-graphes bipartis complets, doit comporter au moins $k$ sous-graphes. De manière équivalente, leur conjecture dit que des unions de $k$ graphes bipartis complets sans arêtes communes peuvent toujours être colorés en au plus $k+1$ couleurs. La conjecture a été invalidée par Huang et Sudakov en 2012, qui ont construit des familles de graphes qui sont des unions disjointes de $k$ graphes bipartis complets et qui requièrent $\Omega (k^{6/5})$ couleurs.

### Partition biclique

Le problème de la partition biclique prend en entrée un graphe non orienté quelconque, et demande de fournir une partition de ses arêtes en un nombre minimal de graphes bipartis complets. Ce problème est NP-difficile, mais fixed-parameter tractable. le meilleur algorithme d'approximation connu pour ce problème a un facteur d'approximation en $O(n/\log n)$$^,$.