Graphe d'amitié

Le graphe d'amitié F_n peut être construit en joignant n copies du graphe cycle C₃ avec un sommet commun[2].

Par construction, le graphe d'amitié F_n est isomorphe au graphe moulin Wd(3, n). C'est un graphe distance unitaire avec maille 3, diamètre 2 et rayon 1. Le graphe F₂ est isomorphe au graphe papillon.

Le théorème de l'amitié de Paul Erdős, Alfréd Rényi et Vera T. Sós de 1966[3] affirme que les graphes finis avec la propriété que deux sommets quelconques ont exactement un voisin en commun sont exactement les graphes d'amitié.

De manière informelle, le théorème dit que si, dans un groupe de personnes, chaque paire de personnes a exactement un ami en commun, alors il doit y avoir une personne qui est l'amie de toutes les autres.

Pour les graphes infinis, ce théorème n'est plus valable : il peut exister de nombreux graphes différents de même cardinalité et qui ont cette propriété[4].

Une preuve combinatoire du théorème d'amitié a été donnée par Mertzios et Unger[5]. Une autre preuve a été donnée par Craig Huneke[6]. Une preuve formalisée dans Metamath été donnée par Alexander van der Vekens en octobre 2018 sur la liste de diffusion Metamath[7].

Le graphe de l'amitié a le nombre chromatique 3 et l'indice chromatique 2n. Son polynôme chromatique peut être déduit du polynôme chromatique du graphe cyclique C₃ ; il est égal à ${\displaystyle (x-2)^{n}(x-1)^{n}x}$.

Le graphe d'amitié F_n est gracieux aux arêtes si et seulement si n est impair. Il est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 1 (mod 4)[8] - [9].

Chaque graphe d'amitié est un graphe à facteur critique (en).

Selon la théorie des graphes extrémaux, tout graphe qui a suffisamment d'arêtes (par rapport à son nombre de sommets) doit contenir un ${\displaystyle k}$-éventail en sous-graphe. Plus précisément, c'est le cas d'un graphe à ${\displaystyle n}$ sommets si le nombre d'arêtes est

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}$

où ${\displaystyle f(k)=k^{2}-k}$ si ${\displaystyle k}$ est impair, et ${\displaystyle f(k)=k^{2}-3k/2}$ si ${\displaystyle k}$ est pair. Ces bornes généralisent le théorème de Turán sur le nombre d'arêtes dans un graphe sans triangle, et ce sont les meilleures bornes possibles pour ce problème, en ce sens que pour tout nombre d'arêtes plus petit, il existe des graphes qui ne contiennent pas de ${\displaystyle k}$-éventail[10].

• Théorème de Ramsey
• Coloration de graphe
• Théorème des amis et des étrangers

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