Théorie extrémale des graphes

Margaret Bilu

1 Rappels sur les graphes

Un graphe est donné par un ensemble V (de l'anglais  vertex ) de sommets, ainsi qu'un
ensemble E (de l'anglais  edge ) d'arêtes, chaque arête reliant deux sommets entre eux. Dans
ce cours, nous allons supposer les graphes nis, c'est-à-dire que V et E sont des ensembles nis.
Nous allons de plus supposer qu'il y a au plus une arête entre deux sommets, et qu'il n'y a pas de
boucles, c'est-à-dire d'arêtes reliant un sommet à lui-même. Le degré d'un sommet est le nombre
d'arêtes qui en partent, c'est-à-dire le nombre de sommets qui sont reliés à lui. Le degré d'un
sommet v sera noté d(v), et l'ensemble des sommets reliés (on dira aussi adjacents ) à v sera noté
D(v). Un ensemble de sommets sans aucune arête est appelé ensemble de sommets indépendants.
Nous noterons, pour tout n ≥ 1, Kn le graphe complet à n sommets, c'est-à-dire le graphe à
n sommets dont tout couple de sommets est relié par une arête. Plus généralement, le graphe à n
sommets obtenu en partitionnant l'ensemble des sommets en r sous-ensembles disjoints V1 , . . . , Vr
de cardinaux respectifs n1 , . . . , nr (de sorte que V = V1 ∪ . . . ∪ Vr et n = n1 + . . . + nr ) et en
reliant entre eux tous les couples de sommets n'appartenant pas à un même Vi est appelé graphe
multipartite complet correspondant à la partition P n1 , . . . , nr et noté Kn1 ,...,nr .
On rappelle le lemme des poignées de mains : v∈V d(v) = 2|E|.
Pour d'autres rappels et précisions sur la notion de graphe, nous vous invitons à consulter
l'excellent polycopié de P. Bornsztein, disponible sur le site d'Animath.

2 Introduction au problème
Dans ce qui suit, nous allons nous intéresser à la présence ou non de sous-graphes complets
dans un graphe. Si un graphe G a 4 sommets, et qu'il ne contient aucun K3 (on dit qu'il est
 sans triangle , alors on peut facilement se convaincre qu'il a au plus 4 arêtes (parmi les 6 arêtes
possibles).

Figure 1  Graphes à 4 sommets sans et avec triangle

Regardons maintenant parmi les graphes à 5 sommets, notés A, B, C, D, E . Un tel graphe a au
plus 52 = 10 arêtes. S'il est sans triangle, il a au moins un sommet de degré inférieur ou égal à 2.

En eet, sinon, quitte à renommer les sommets, nous pouvons supposer que A est relié à B, C, D.
B étant également de degré au moins 3, il est relié à C ou à D, ce qui nous fait un triangle.
Nous pouvons donc supposer que le sommet A par exemple est de degré au plus 2. D'autre part,
d'après notre étude des graphes à 4 sommets, pour que notre graphe soit sans triangle, il faut que
le nombre d'arêtes reliant deux sommets parmi B, C, D, E soit au plus 4. Un graphe à 5 sommets

1
sans triangle a donc au plus 6 arêtes. De plus, notre raisonnement nous donne automatiquement
un exemple d'un tel graphe sans triangle, qui n'est autre que le graphe bipartite complet K2,3 :

C'est ce genre d'idées que nous allons généraliser dans ce cours, an de préciser le fait intuitif
selon lequel un graphe ayant susamment d'arêtes contiendra des triangles, et même des graphes
complets plus gros. Nous allons donc nous intéresser à la notion suivante :
Dénition 1. Soit m ≥ 3 un entier. On dit qu'un graphe G est m-libre s'il ne contient pas Km
comme sous-graphe. Un graphe 3-libre sera aussi appelé graphe sans triangle.
Remarquons que la notion de graphe multipartite (avec r ensembles de sommets indépendants)
ci-dessus nous donne un exemple de graphe (r + 1)-libre, vu que parmi r + 1 sommets, nous en
aurons toujours deux dans le même ensemble de sommets indépendants, donc non reliés par une
arête. En particulier, les graphes bipartites donnent des exemples de graphes sans triangle.

3 Graphes sans triangle : théorème de Mantel

Théorème 2. (Mantel) Si G est un graphe à n sommets sans triangle, alors il a au plus b n4 c
2

arêtes. De plus, le seul graphe à n sommets sans triangle ayant exactement b n4 c arêtes est le
2

graphe bipartite Kb n2 c,d n2 e .

Démonstration. Nous allons présenter plusieurs preuves de ce théorème pour illustrer les dié-
rentes méthodes que l'on peut employer dans ce cadre. L'initialisation des récurrences a été faite
dans le paragraphe d'introduction, et on suppose donc dans les preuves que n > 4. Le cas d'égalité
ne sera traité que dans la première preuve, l'approche étant similaire pour les autres.
1. Récurrence en supprimant une arête. Soit uv une arête dans le graphe G. Puisque u et
v n'ont pas de voisin commun, nous avons d(u) + d(v) ≤ n. Si on supprime les sommets u et
v , nous obtenons un graphe sans triangle à n − 2 sommets, qui par hypothèse de récurrence
2
a au plus b (n−2) 4
c arêtes. Ainsi, le nombre d'arêtes du graphe de départ est inférieur ou égal
(n−2)2
à b 4 c + n − 1 = b n −4n+4
2 2
4
c + n − 1 = b n4 c.
Pour le cas d'égalité, il faut que toutes les inégalités ci-dessus soient des égalités. Ainsi,
d(u) + d(v) = n, c'est-à-dire que D(u) ∪ D(v) = V . Puisque G est sans triangle, D(u) et
D(v) sont des ensembles de sommets indépendants, donc G est bipartite. Le graphe bipartite
complet Km,n−m a m(n − m) arêtes, grandeur qui est maximale en m = b n2 c. On vérie que
b n2 cd n2 e = b n4 c séparément pour n pair et n impair.
2

2. Récurrence en supprimant un sommet. On suppose que c'est vrai pour tous les graphes
à n − 1 sommets. Soit un graphe à n sommets. Alors il a nécessairement un sommet de degré
inférieur ou égal à b n2 c : sinon, choisissons un sommet v1 . Parmi les sommets adjacents à v1 ,
choisissons un sommet v2 . Nous avons |D(v1 )| ≥ 1 + b n2 c et |D(v2 )| ≥ 1 + b n2 c, d'où
jnk n
|D(v1 ) ∩ D(v2 )| = |D(v1 )| + |D(v2 )| − |D(v1 ) ∪ D(v2 )| ≥ 2 + 2 −n>2 − n ≥ 0.
2 2
Donc il existe un sommet v3 ∈ D(v1 ) ∩ D(v2 ), ce qui nous fait un triangle.

2
 Soit donc un sommet vn de degré inférieur ou égal à b n2 c. Par hypothèse de récurrence, le
graphe à n − 1 sommets sans triangle obtenu en supprimant vn et toutes les arêtes qui en
2 (n−1)2
partent a au plus b (n−1)
4
c arêtes. Donc notre graphe à n sommets a au plus b 4
c + b n2 c
2
arêtes. Cette dernière quantité est inférieure à b (n−1) + n2 c = b n 4+1 c. Puisqu'un carré est
2
4
toujours congru à 0 ou à 1 modulo 4, nous avons b n 4+1 c = b n4 c, ce qui conclut.
2 2

3. Inégalités Pour toute arête uv , nous avons d(u) + d(v) ≤ n comme ci-dessus. En sommant
cela sur toutes les arêtes uv , on obtient
X
(d(u) + d(v)) ≤ |E|n.
uv∈E

Dans le côté gauche, chaque terme d(u) apparaît autant de fois qu'il y a d'arêtes partant de
u, donc d(u) fois. Ainsi, on a
X X
(d(u) + d(v)) = d(u)2 .
uv∈E u∈V

Nous savons que d(u) = 2|E| (lemme des poignées de mains). Par Cauchy-Schwarz,
P
u∈V
on a
!2
X 1 X |E|2
|E|n ≥ d(u)2 ≥ d(u) =2 ,
u∈V
n u∈V
n

d'où |E| ≤ n2
4
.

4 Estimation du nombre de triangles

Soit G un graphe, et soient
T0 = {ensembles de trois sommets de G deux-à-deux non reliés}
T1 = {ensembles de trois sommets de G tels qu'exactement deux d'entre eux soient reliés.}
T2 = {ensembles de trois sommets de G tels qu'exactement deux d'entre eux soient non reliés.}
ainsi que T3 l'ensemble des triangles.
Ce premier lemme précise la technique utilisée dans la troisième preuve du théorème de Mantel :
Lemme 3. On a |T3 | ≥ 1
P
3 uv∈E (d(u) + d(v) − n)
Démonstration. Le nombre de triangles ayant pour côté uv est
|D(u) ∩ D(v)| = |D(u)| + |D(v)| − |D(u) ∪ D(v)| ≥ d(u) + d(v) − n.

Puisque chaque triangle a trois côtés, chaque triangle est compté trois fois dans la somme
X
(d(u) + d(v) − n),
uv∈E

d'où le résultat.
Lemme 4. On a
1X
|T1 | + |T2 | = (d(u)(n − 1 − d(u))).
2 u∈V

3
Démonstration. La somme u∈V (d(u)(n − 1 − d(u))) compte le nombre de triplets (x, y, z) avec
P
x, y reliés par une arête et z non relié à x. Les éléments de T1 sont en correspondance exacte avec
les paires de triplets de la forme {(x, y, z), (y, x, z)} avec x et y reliés, x et z non reliés et y et z
non reliés. Les paires de T2 sont quant à elles en correspondance exacte avec les paires de triplets
de la forme {(x, y, z), (z, y, x)} avec x et y reliés, x et z non reliés et y et z reliés. Chaque élément
de T1 ∪ T2 est donc compté exactement deux fois dans la somme considérée, d'où le résultat.
Lemme 5. On a X d(u)
|T2 | + 3|T3 | = .
u∈V
2

Démonstration. Pour chaque sommet u, le terme d(u) compte le nombre de couples de sommets


2
parmi les voisins de u. Chaque élément de T2 est donc compté exactement une fois, et chaque
triangle est compté trois fois, une fois pour chaque sommet, d'où le résultat.

5 Sommets de petit degré

Dans la deuxième preuve du théorème de Mantel, nous avons montré que l'absence de triangles
force l'existence d'un sommet de  petit  degré. Le résultat suivant donne une borne explicite
sur le degré d'un tel sommet, dans le cas des triangles mais aussi dans le cas de graphes complets
plus gros.
Lemme 6. (Zarankiewicz) Soit k ≥ 3 un entier. Si G est un graphe k-libre à n sommets, alors il
existe un sommet de degré inférieur ou égal à b k−2
k−1
nc.

Démonstration. Dans cette preuve nous utilisons à répétition le fait que pour deux sous-ensembles
de sommets A et B de G,

|A ∩ B| = |A| + |B| − |A ∪ B| ≥ |A| + |B| − n. (1)

Supposons que la conclusion du lemme soit fausse, en prenons un sommet v1 . On peut choisir
v2 ∈ D(v1 ), et de plus d'après (1),
 
k−2
|D(v1 ) ∩ D(v2 )| ≥ d(v1 ) + d(v2 ) − n > 2 n − n > 0,
k−1

donc il existe v3 ∈ D(v1 ) ∩ D(v2 ). Soit j ≤ k − 1, et supposons construits des sommets v1 , . . . , vj

tels que pour tout ` ∈ {2, . . . , ` − 1}, v` ∈ ∩`−1
i=1 V (vi ) et
  
k−2
∩ji=1 D(vi ) ≥j 1+ n − (j − 1)n.
k−1

Puisque j ≤ k − 1, on a
k−2
∩ji=1 D(vi ) > j n − (j − 1)n ≥ (k − 2)n − (j − 1)n ≥ 0,
k−1

donc il existe vj+1 ∈ ∩ji=1 D(vi ), et de plus

  
k−1
∩j+1
i=1 D(vi ) ≥ ∩ji=1 D(vi ) + |D(vj+1 )| − n ≥ (j + 1) 1 + n − jn.
k−2

On construit ainsi par récurrence des sommets v1 , . . . , vk formant un graphe complet à k

sommets, contradiction.

4
Exercice 1 Soit un ensemble de 2013 points tel que parmi trois quelconques de ces points, il y
en ait toujours deux à distance inférieure ou égale à 1. Montrer qu'alors il en existe 1007 que l'on
peut recouvrir avec un disque de rayon 1.
Solution de l'exercice 1 On considère le graphe dont les sommets sont les points, et une arête relie
deux points si la distance entre ceux-ci est strictement supérieure à 1. Il existe un sommet v de
degré inférieur ou égal à b 2013
2
c = 1006. Cela veut dire qu'il existe 2012 − 1006 = 1006 points qui
ne sont pas reliés à v , et qui sont donc à distance inférieure ou égale à 1 de lui. Le disque de centre
v et de rayon 1 répond à la question.

6 Le théorème de Turán
Dans ce qui précède, nous avons vu que pour obtenir un graphe sans triangle, il sut de
prendre un graphe bipartite, c'est-à-dire un graphe constitué de deux ensembles de sommets
indépendants, car alors tout ensemble de trois sommets a au moins deux sommets dans l'un de
ces deux ensembles de sommets indépendants. De plus, le théorème de Mantel dit que si à nombre
de sommets n xé on veut maximiser le nombre d'arêtes, il faut que le graphe bipartite soit
complet et que les sommets soient équirepartis autant que possible entre les deux ensembles de
sommets indépendants.
En s'inspirant de cela, on trouve facilement un moyen de construire à coup sûr un graphe s+1-
libre pour tout s ≥ 2 : il sut de prendre un graphe multipartite avec s ensembles de sommets
indépendants. Fixons maintenant le nombre n de sommets. Si on veut maximiser le nombre
d'arêtes, cela paraît judicieux de repartir les sommets aussi équitablement que possible entre les
ensembles de sommets indépendants. On pose donc la division euclidienne n = as + b de n par s,
et on considère le graphe s-partite complet Ka+1,...,a+1,a...,a où a + 1 apparaît b fois et a apparaît
s − b fois. Autrement dit, on met a + 1 sommets dans b ensembles de sommets indépendants, et
a sommets dans les autres, et on relie tous les sommets appartenant à des ensembles de sommets
indépendants distincts. On notera se graphe T (n, s) et on l'appellera graphe de Turán. On note
t(n, s) son nombre d'arêtes.

Figure 2  Le graphe T (8, 3)

Remarque 7. L'entier a ci-dessus n'est autre que b nr c, et T (n, r) = Kd nr e,...,d nr e,b nr c,...,b nr c , où d nr e
intervient b fois.
Exercice 1 Montrer que t(n−s, s)+(n−s)(s−1)+ s
= t(n, s). En déduire que t(n, s) ≤ b s−1 n2 c.


2 2s

Solution de l'exercice 1 Si n = as + b est la division euclidienne de n par s, celle de n − s par s

s'obtient simplement en remplaçant a par a − 1. Ainsi, T (n − s, s) s'obtient à partir de T (n, s) en
enlevant un sommet dans chaque ensemble de sommets indépendants. Cela enlève d'une part les
arêtes entre deux sommets supprimés, qui sont au nombre de 2 , et d'autre part les arêtes ayant
s

exactement une extrémité parmi les sommets supprimés : il y en a (n − s)(s − 1), car choisir une
telle arête revient à choisir l'un des n − s sommets non supprimés, ainsi que l'un des s − 1 sommets
supprimés qui ne sont pas dans le même ensemble de sommets indépendants. Une récurrence sur
a permet ensuite de prouver la borne demandée.

5
Remarque 8. On peut montrer plus précisément que
s − 1 n 2 − b2
 
b
t(n, s) ≤ +
s 2 2
arêtes, où b est le reste de la division euclidienne de n par s.
Théorème 9. (Turán) Si un graphe G à n sommets est s + 1-libre alors son nombre d'arêtes est
inférieur ou égal à t(n, s). De plus, il y a égalité si et seulement si G = T (n, s).
Autrement dit, de même que dans le cas des graphes sans triangles, le graphe de Turán
maximise le nombre d'arêtes que peut avoir un graphe r-libre.
Démonstration. On fait une récurrence sur a = b ns c. Si a = 0
, le graphe a strictement moins de s
sommets donc est nécessairement s + 1-libre, et moins de 2 = 2 = t(n, s) arêtes.
n b

Supposons que la conclusion est vraie pour a − 1, et considérons un graphe G à n sommets,

s + 1 libre, ayant un nombre maximal d'arêtes, c'est-à-dire que l'ajout de n'importe quelle arête
ferait apparaître un Ks+1 . Cette dernière supposition implique que G contient une copie H de
Ks . Par s + 1-liberté, chaque sommet n'appartenant pas à H est relié à au plus s − 1 sommets
de H . De plus, le graphe G\H est Ks+1 libre et possède n − s = (a − 1)s + b sommets, donc par
hypothèse de récurrence il a au plus t(n − s, s) arêtes. Le nombre d'arêtes de G est donc au plus
 
s
t(n − s, s) + (n − s)(s − 1) + .
| {z } | {z } 2
arêtes de G\H arêtes entre H et G\H |{z}
arêtes de H

D'après l'exercice ci-dessus, cette expression vaut exactement t(n, s).

7 Exercices
Exercice 1 Soit G un graphe tel que la moyenne des degrés de ses
sommets soit supérieure ou
égale à (1/2 + c)n, avec c > 0. Montrer que G contient au moins c n
3
triangles.
Exercice 2 Soit G un graphe de degré moyen d. Montrer que G contient un sous-graphe H dont
tous les sommets sont de degré supérieur ou égal à d
2

Exercice 3 Il y a n participants à un colloque, chacun connaissant au plus k langues. Pour chaque

groupe de trois participants, il y en a au moins deux qui parlent une même langue. Trouver la
plus petite valeur de n telle que pour toute distribution de langues satisfaisant ces propriétés, on
puisse trouver une langue parlée par au moins trois délégués.
Exercice 4 On considère 21 points sur un cercle. Montrer qu'au moins 100 paires de ces points
dénissent un angle au centre inférieur ou égal à 120◦ .
Exercice 5 Soit n ≥ 2 un entier. On appelle intervalle un sous-ensemble A ⊆ {1, . . . , n} tel qu'il
existe 1 ≤ a < b ≤ n tels que A = {a, a + 1, . . . , b − 1, b}. Soient A1 , . . . , AN des sous-ensembles
de {1, . . . , n} tels que si 1 ≤ i < j ≤ n alors Ai ∩ Aj est un intervalle. Montrer que N ≤ b n4 c et
2

que cette borne est optimale.

Exercice 6 Montrer qu'un graphe à n sommets et m arêtes a au moins 3n
m
(4m − n2 ) triangles.
√
Exercice 7 Soit G un graphe de n sommets ayant au moins 21 n n − 1 arêtes. Montrer qu'il
contient un triangle ou un 4-cycle.
Exercice 8 Il y a 1991 participants à un événement sportif. Chacun d'eux connait au moins n
autres participants (le fait de se connaître est réciproque). Quelle est la valeur minimale de n pour
laquelle il existe nécessairement un groupe de 6 participants se connaissant deux à deux ?

6
Exercice 9 (IMO 2003) Soit A un sous-ensemble de S = {1, 2, . . . , 1000000} ayant exactement
101 éléments. Montrer qu'il existe t1 , . . . , t100 ∈ S tels que les ensembles Aj = {x + tj |x ∈ A}
soient disjoints.
Exercice 10 Soit G un graphe. Montrer qu'il contient un ensemble de sommets indépendants de
cardinal supérieur ou égal à
X 1
.
v∈V
1 + d(v)

Exercice 11 Soit n ≥ 2, et soit G un graphe avec 2n sommets et n2 + 1 arêtes. Montrer que G

contient K4 privé d'une arête (ou, autrement dit, deux triangles avec un côté en commun).
Exercice 12 Soit G un graphe 4-libre, et tel que son nombre de sommets soit un multiple de
trois. Quel est le nombre maximal de triangles de G ?
Exercice 13
1. (Théorème de Dirac) Soit un graphe G à n ≥ 3 sommets tel que les degrés de tous ses
sommets soient supérieurs ou égaux à n2 . Montrer que G admet un cycle hamiltonien, c'est-
à-dire qu'il est possible de parcourir tous les sommets du graphe une et une seule fois et de
revenir au point de départ.
2. Soit un graphe G à n ≥ 3 sommets tel que les degrés de tous ses sommets soient supérieurs
ou égaux à n+12
. Montrer qu'alors pour toute arête e, G admet un cycle hamiltonien passant
par e.
Exercice 14 Dans un pays, il y a n ≥ 5 villes, desservies par deux compagnies aériennes. Tout
couple de villes est relié par au plus une des deux compagnies aériennes (une liaison est toujours
dans les deux sens). Une restriction gouvernementale impose que, si on enchaîne strictement moins
de 6 vols avec une même compagnie, on ne puisse pas se retrouver dans la ville d'où on est parti.
Montrer que ces deux compagnies orent à elles deux moins de b n3 c.
2

Exercice 15 (Shortlist 2001) Soit G un graphe ni 5-libre, et tel que deux triangles ont toujours
au moins un sommet en commun. Montrer qu'il sut d'enlever au plus deux sommets pour que
le graphe ne contienne plus de triangles.
Exercice 16 (Shortlist 2012) On se donne 2500 points sur un cercle, numérotés 1, . . . , 2500 dans
un certain ordre. Montrer que l'on peut choisir 100 cordes reliant certains de ces points, disjointes
deux à deux, et telles que, si pour chaque corde on calcule la somme des deux nombres situés à
ses extrémités, on obtienne 100 sommes distinctes.

8 Solutions
Solution de l'exercice 1 Notons d la moyenne des degrés des sommets. Soit uv ∈ E une arête. Le
nombre de triangles contenant E est égal à

|D(u) ∩ D(v)| ≥ d(u) + d(v) − n.

En sommant sur toutes les arêtes, vu que chaque triangle correspond à trois arêtes, le nombre de
triangles est au moins égal à
1 X
(d(u) + d(v) − n).
3 uv∈E

7
Chaque terme d(u) dans cette somme est compté autant de fois qu'il y a d'arêtes uv , donc d(u)
fois. Ainsi, le nombre de triangles est supérieur ou égal à
!
1 X 1
d(v)2 − n|E| ≥ (nd2 − n|E|)
3 v∈V
3
1 n
= nd(d − ).
3 2
Si d = cn+ n2 , alors on obtient que le nombre de triangles est supérieur ou égal à 13 cdn. En utilisant
que d ≥ n2 , on obtient le résultat.
Solution de l'exercice 2 Nous allons enlever les sommets de G un à un jusqu'à arriver un tel sous-
graphe. Le nombre total d'arêtes est nd2
. S'il existe un sommet de degré inférieur strictement à d2 ,
on l'enlève. Cela enlève < 2 arêtes. Ce processus doit nécessairement se terminer, vu que sinon le
d

nombre d'arêtes sera toujours strictement positif quand on aura enlevé tous les sommets.
Solution de l'exercice 3 Remarquons d'abord que n ≥ 2k + 3. En eet, si
n = 2k + 2, répartissons
les participants en deux groupes de k + 1 personnes. On prend 2 2 langues diérentes, que
k+1

l'on distribue parmi les couples de personnes d'un même groupe, de sorte que deux personnes
n'appartenant pas au même groupe ne puissent pas communiquer. Dès qu'on prend trois personnes,
il y en a deux qui appartiennent au même groupe, et ont donc une langue en commun.
Montrons maintenant que n = 2k + 3 convient. Considérons le graphe à 2k + 3 sommets dont
les sommets sont les participants du colloque, et les arêtes relient deux participants n'ayant pas
de langue en commun. D'après l'énoncé, ce graphe est sans triangle. Pour faire apparaître trois
personnes parlant la même langue, il faut faire apparaître  beaucoup de personnes parlant la
même langue qu'un certain individu A, car alors deux d'entre elles auront une langue en commun
parce que le nombre de langues parlées par A est limité. Il faut donc faire apparaître un sommet
de petit degré dans ce graphe. Or nous savons qu'il existe un sommet A de degré b 2k+3 2
c ≥ k + 1.
Il existe donc k + 1 participants A1 , . . . , Ak+1 pouvant communiquer avec A. Or A ne parle qu'au
plus k langues, donc il existe deux participants Ai et Aj parlant la même langue parmi ces k
langues. A, Ai , Aj ont donc une langue en commun.
Remarque 10. La disposition pour n = 2k + 2 est exactement le graphe de Turán T (2k + 2, 2).

Solution de l'exercice 4 Trouvons le bon graphe sans triangle : on relie deux points si l'angle au
centre qu'ils dénissent est strictement supérieur à 120◦ . Trois tels points ne sont alors jamais
reliés deux à deux, donc le graphe est sans triangle. Le nombre d'arêtes

est alors inférieur ou égal
à 212 /4, donc à 110. Dans le graphe complémentaire il y a donc 212 − 110 = 100 arêtes, ce qui
conclut.
Solution de l'exercice 5 La borne à montrer suggère de ramener le problème à la construction d'un
graphe sans triangle à n sommets et N arêtes. On construit un graphe G dont les sommets sont
les entiers 1, . . . , n, et où deux entiers a et b sont reliés par une arête s'il existe i ∈ {1, . . . , N } tel
que a = min Ai et b = max Ai . Si Ai et Aj vérient {min Ai , max Ai } = {min Aj , max Aj }, alors,
puisque Ai ∩ Aj est un intervalle, Ai = Aj . Le nombre d'arêtes du graphe est donc exactement
N . De plus, ce graphe est sans triangle : en eet, soient trois entiers a < b < c reliés deux à
deux, et i, j ∈ {1, . . . , N } tels que Ai et Aj correspondent respectivement aux arêtes ab et bc.
Alors Ai ∩ Aj ⊂ {b}, impossible car un intervalle a au moins deux éléments (cela prouve plus
généralement qu'un entier n'est relié qu'à des entiers soit tous plus grands, soit tous plus petits
que lui, c'est-à-dire qu'il ne peut pas être maximum et minimum en même temps).
D'après le théorème de Mantel, nous avons donc la borne cherchée. De plus, elle est atteinte
quand G est le graphe bipartite complet Kb n2 c,d n2 e , les deux ensembles de sommets indépendants
correspondant respectivement à {1, . . . , b n2 c} et à {b n2 c + 1, . . . , n}.

8
Solution de l'exercice 6 Le nombre de triangles est supérieur ou égal à
!
4m2
 
1 X 1 X
2 1 m
4m − n2 .


(d(u) + d(v) − n) ≥ d(u) − nm ≥ − nm =
3 uv∈E 3 u∈V
3 n 3n

Solution de l'exercice 7 Supposons le contraire, et soit un sommet x de degré d(x) = d. Montrons

d'abord X
deg(y) ≤ n − 1
y adjacent à x

Deux voisins de x quelconques ne sont pas reliés car notre graphe n'a pas de triangle. Donc
un sommet compté dans la somme du côté gauche est nécessairement soit x (qui est compté d
fois, une fois pour chaque y adjacent à x), soit l'un des n − d − 1 sommets autres que x ou ses
voisins. Si un tel sommet est compté deux fois, c'est qu'il est relié à deux voisins de x, or cela
n'est pas possible car cela créerait un 4-cycle. Ainsi, la somme considérée est inférieure ou égale
à 1 × d + (n − d − 1) × 1 = n − 1.
Or X X X 1 1
n(n − 1) ≥ deg(y) = deg(y)2 ≥ (deg(y))2 = (2|E|)2 ,
x∈V y adjacent à x y∈V
n n
d'où le résultat.
Solution de l'exercice 8 On construit un graphe dont les sommets sont les participants, reliés par
une arête lorsqu'ils se connaissent. Alors tout sommet est de degré au moins n, et on cherche la
valeur minimale de n pour laquelle ce graphe contient nécessairement K6 . D'après le lemme de
Zarankiewicz, un graphe 6-libre à 1991 sommets contient au moins un sommet de degré inférieur
ou égal à b 4×1991
5
c = 1592. Le borne n ≥ 1593 est donc susante. D'autre part, elle est optimale
si on considère le graphe de Turán 6-libre T (1991, 5). Ce graphe est le graphe complet 5-partite
avec 399 arêtes dans une des parties et 398 dans les autres. Le degré minimal d'un sommet de se
graphe est par conséquent 1991 − 399 = 1592.
Solution de l'exercice 9 L'énoncé nous invite à considérer le graphe dont les sommets sont les
éléments de S et tel que deux sommets a et b sont reliés si les ensembles {x + a|x ∈ A} et
{x + b|x ∈ A} sont disjoints. On veut montrer que ce graphe n'est pas 100-libre. Pour utiliser
le théorème de Turán, on va chercher à minorer le nombre d'arêtes du graphe. Deux éléments
distincts a et b de S sont reliés si et seulement si pour tous x, y ∈ A, on a x − y 6= a − b. Comme
l'ensemble A a 101 éléments, cela fait au plus 101 × 100 diérences possibles. Ainsi, pour un
élément a de S xé, il y a au plus 101 × 100 sommets non reliés à a dans G, c'est-à-dire que le
degré de tout sommet de G est supérieur ou égal à 106 − 10100 − 1. G a donc au moins
1X 106 (106 − 10100 − 1)
d(v) ≥
2 a∈V 2

arêtes. Il reste à vérier que cette dernière valeur est supérieure à 2×99
98
(106 )2 , c'est à dire que
99(106 − 10101) > 98 × 106 , donc 106 ≥ 99 × 10101 = 999999, ce qui est vrai.
Solution de l'exercice 10 Notons f (G) = v∈G 1+d(v) 1
. On raisonne par récurrence sur le nombre
P
n de sommets de G. Quand n = 1, c'est clair. Supposons que c'est vrai pour tous les graphes à
n − 1 sommets, et considérons G à n sommets. Soit v0 un sommet de degré minimal d dans G, et
v1 , . . . , vd ses voisins. On considère le graphe G0 obtenu à partir de G en supprimant les sommets
v0 , . . . , vd . Si G0 est vide, alors d = n − 1 et par minimalité de d, G est le graphe complet à n
sommets et f (G) = n × n1 = 1, donc la conclusion est clairement vraie.
Supposons maintenant que G0 est non vide. Alors par hypothèse de récurrence, G0 contient un
ensemble I 0 de sommets indépendants de cardinal supérieur ou égal à f (G0 ), et I := I 0 ∪ {v0 } est
un ensemble de sommets indépendants dans G.

9
 Si on note d0 (v) le degré d'un sommet v de G0 , nous avons clairement d0 (v) ≤ d(v). De plus,
pour tout i, d(vi ) ≥ d = d(v0 ) Nous avons donc
d
0
X 1 X 1 1+d
f (G ) = 0
= f (G) − ≥ f (G) − = f (G) − 1,
v∈G0
1 + d (v) i=0
1 + d(vi ) 1 + d

d'où
|I| ≥ |I 0 | + 1 ≥ f (G0 ) + 1 ≥ f (G),
ce qui conclut.
Solution de l'exercice 11 On raisonne par récurrence sur n. Pour n = 2, c'est clair. Supposons que
c'est vrai pour n, et considérons un graphe G avec 2(n + 1) = 2n + 2 sommets et (n + 1)2 + 1 =
n2 + 2n + 2 arêtes. D'après le théorème de Mantel, il contient un triangle formé de trois sommets
u, v, w. Parmi les sommets du triangle, il y en a deux, disons u et v , dont les degrés ont la même
parité. Considérons le sous-graphe de G obtenu en supprimant u et v ainsi que les arêtes qui
en partent. Si le sous-graphe en question a au moins n2 + 1 arêtes, on a ni par hypothèse de
récurrence. Sinon, cela veut dire qu'au moins 2n + 2 arêtes de G ont au moins une extrémité
appartenant à l'ensemble {u, v}. Puisque u et v sont reliés par une arête, le nombre de telles
arêtes est également donné par la quantité d(u) + d(v) − 1, qui est impaire car d(u) et d(v) sont
de même parité. Ainsi,
d(u) + d(v) − 1 ≥ 2n + 2.
Le nombre d'arêtes partant de u ou de v et diérentes de uv , uw, vw est donc supérieur ou égal
à 2n. Puisqu'il n'y a que 2n − 1 sommets diérents de u, v, w, par le principe des tiroirs il y en a
au moins relié relié aussi bien à u qu'à v , ce qui conclut.
Solution de l'exercice 12 Pour toute arête e, on note d(e) le nombre de triangles ayant l'arête e
pour côté, autrement dit, le nombre de sommets reliés aux deux extrémités de e. Nous allons
adopter la méthode de comptage de triangles ci-dessus en utilisant cette notion de degré d'une
arête à la place du degré d'un sommet.
Soit 3k le nombre de sommets de G. Nous allons commencer par montrer que si e, f, g sont
trois arêtes formant un triangle,

d(e) + d(f ) + d(g) ≤ 3k.

En eet, dans le cas contraire, par le principe des tiroirs il existe nécessairement un sommet du
graphe, diérent des extrémités de e, f, g , qui est compté deux fois dans le côté gauche, donc qui
est sommet de deux triangles ayant deux de ces arêtes pour côté. Or cela impliquerait l'existence
d'un K4 , contradiction.
En notant t le nombre de triangles et en sommant l'inégalité ci-dessus sur tous les triangles,
on obtient X
(d(e) + d(f ) + d(g)) ≤ 3kt.
triangles

Dans la somme du côté gauche, chaque d(e) est compté autant de fois qu'il y a de triangles
contenant e, donc d(e) fois. Ainsi, le côté gauche vaut arêtes d(e)2 . On applique ensuite l'inégalité
P
de Cauchy-Schwarz pour obtenir :

( arêtes d(e))2
X P
2
3kt ≥ d(e) ≥
arêtes
m
où l'on note m le nombre d'arêtes du graphe. Dans la somme arêtes d(e), chaque triangle est
P
compté trois fois (une fois pour chacun de ses côtés), elle vaut donc 3t.

10
 2
Nous avons donc mk ≥ 3t. D'autre part, d'après le théorème de Turán, m ≤ (3k3 ) = 3k 2 . Nous
avons donc t ≤ k 3 .
Réciproquement, pour montrer que ce résultat est optimal, le fait que nous ayons utilisé le
théorème de Turán pour le démontrer nous suggère de considérer le graphe de Turán Kk,k,k , 4-libre
car tripartite. Le nombre de triangles est clairement k 3 .
Solution de l'exercice 13
1. On raisonne par l'absurde, et on prend parmi les graphes à n sommets pour lesquels le
résultat à montrer n'est pas vrai, un graphe G avec un nombre d'arêtes maximal. Ainsi,
l'ajout de n'importe quelle arête à G (ce qui ne change pas le fait que les degrés sont
supérieurs ou égaux à n2 ) fait apparaître un cycle hamiltonien.
Soient x et y deux sommets non adjacents. Puisque l'ajout de l'arête xy crée un cycle
hamiltonien, il existe un chemin hamiltonien (c'est-à-dire parcourant tous les sommets du
graphe une et une seule fois) x = z1 , z2 , . . . , zn−1 , zn = y allant de x à y . Les ensembles
{i : x adjacent à zi+1 }

et
{i : y adjacent à zi }
sont tous les deux contenus dans {1, . . . , n − 1}, et de cardinal supérieur ou égal à n2 , donc ils
ont une intersection non vide. Soit j un élément de cette intersection. Alors x est adjacent
à zj+1 et y est adjacent à zj , donc on obtient un cycle hamiltonien
y, z2 , . . . , zj , z, zn−1 , . . . , zj+1 , y,

contradiction.
2. Soient x et y les extrémités de l'arête e. D'après la question précédente, il existe un cycle
hamiltonien H . S'il passe par e, on a ni. Sinon, soit x0 le successeur de x, et y 0 celui de
y dans ce cycle. On considère le chemin qui commence en x0 , qui parcourt H dans le sens
direct jusqu'en y , puis qui va en x en suivant l'arête e, et qui parcourt H en sens inverse
pour arriver à y 0 . Si x0 et y 0 sont reliés par une arête, on a fabriqué un cycle hamiltonien
contenant e. Sinon, notons
x0 = z1 , z2 , . . . , zk = y, zk+1 = x, zk+2 , . . . , zn = y 0

ce chemin, et considérons les ensembles

{i : x0 adjacent à zi+1 }\k

et
{i : y 0 adjacent à zi }\k.
Ils sont inclus dans l'ensemble {1, . . . , n − 1}\k de cardinal n − 2 et chacun d'eux est de
cardinal supérieur ou égal à n−1
2
, donc ils s'intersectent nécessairement en un entier p 6= k .
Il sut alors de considérer le cycle hamiltonien
x0 = z1 , z2 , . . . , zp , y 0 = zn , zn−1 , . . . , zp+1 , x0 .

Puisque p 6= k , l'arête e = zk zk+1 y appartient bien, ce qui conclut.

Solution de l'exercice 14 On considère le graphe G dont les sommets sont les n villes, deux villes
étant reliées par une arête rouge ou bleue si l'une ou l'autre des deux compagnies propose un
vol direct entre ces villes. L'hypothèse de l'énoncé signie qu'il n'y a pas de 3-, 4- ou 5- cycles
monochromes. Raisonnons par l'absurde et supposons que le nombre d'arêtes est strictement plus

11
grand que b n3 c. Alors d'après le théorème de Turán, G contient K4 . Avec la condition sur les 3-
2

et 4-cycles, on vérie facilement que si on appelle A1 , A2 , A3 , A4 les sommets de cette copie H de

K4 à l'intérieur de G, quitte à les renommer, les arêtes A1 A2 , A2 A3 et A3 A4 sont rouges et les
autres sont bleues.
Regardons alors les n − 4 autres sommets. Chacun de ces sommets ne peut être relié par plus
de deux arêtes à des sommets de H . En eet, s'il y en a 3, il y en a deux de la même couleur, qui
avec celles de H forment soit un 3-cycle, soit un 4-cycle, ce qui contredit l'énoncé.
Cette remarque nous permet d'éliminer les cas 5 ≤ n ≤ 8. En eet, le nombre d'arêtes de
notre graphe est au plus
 
n−4
6 + 2(n − 4) + .
|{z} 2
arêtes de H
| {z }
arêtes entre H et G\H | {z }
arêtes de G\H

On vérie que c'est inférieur à b n3 c pour 5 ≤ n ≤ 8. La conclusion de l'énoncé est donc vraie pour
2

ces valeurs de n.
Supposons donc maintenant que n ≥ 9, et faisons une récurrence, initialisée par ce que nous
venons de montrer : par hypothèse de récurrence, le résultat est vrai pour G\H , graphe à n−4 ≥ 5
2
sommets. Le nombre d'arêtes de G\K est donc inférieur ou égal à (n−4) 3
. Alors le nombre d'arêtes
de G est inférieur ou égal à
(n − 4)2
6 + 2(n − 4) + .
3
2
Nous avons donc 6 + 2(n − 4) + (n−4)
3
≥ n2
3
, ce qui donne n ≤ 5, contradiction.
Solution de l'exercice 15 Nous allons distinguer plusieurs cas.
1. Le graphe contient une copie de K4 , dont nous appellerons les sommets A, B, C, D. Tout
triangle contient alors au moins deux sommets parmi A, B, C, D. Supposons qu'il existe
deux triangles contenant deux paires de sommets disjointes parmi A, B, C, D : sans perte
de généralité, nous pouvons les appeler EAB et F CD. Ces deux triangles ont un sommet
en commun, donc E = F . Nous aboutissons alors à une contradiction car EABCD est
dans ce cas un graphe complet à 5 sommets. Soit maintenant un triangle, que nous pouvons
sans perte de généralité noter EAB . Alors d'après ce qui précède tout autre triangle doit
nécessairement contenir A ou B . Ainsi, il sut de supprimer les points A et B pour ne plus
avoir de triangle.
2. Le graphe ne contient pas K4 , mais contient K4 privé d'une arête, c'est-à-dire deux triangles
partageant un côté. Notons A, B, C, D ces sommets, avec A et D non reliés. Un triangle qui
ne contient ni B , ni C , doit, pour avoir un sommet en commun avec ABC et BCD, contenir
A et D, ce qui est impossible car A et D ne sont pas reliés. Donc tout triangle contient B
ou C . Il sut donc de supprimer B et C .
3. Deux triangles quelconques ont exactement un sommet en commun. Soient ABC et ADE des
triangles, avec B, C, D, E nécessairement tous distincts. Soit un autre triangle, et supposons
qu'il ne contient pas A. Alors sans perte de généralité, nous pouvons supposer qu'il contient
B et D. Cela veut dire que B et D sont reliés, ce qui fait apparaître un triangle ABD ayant
deux sommets en commun avec ABC , contradiction. Ainsi, tout triangle contient A et il
sut de supprimer A.
Solution de l'exercice 16 Dans toute la suite pour simplier nous noterons n = 2499 , de sorte qu'il
y a 2n points numérotés 1, . . . , 2n et que les sommes diérentes possibles aux extrémités d'une
corde sont 3, 4, . . . , 4n − 1. On considère des couleurs que l'on appelle c3 , c4 , . . . , c4n−1 et on colorie
une corde avec la couleur ci si la somme des nombres à ses extrémités est i. Ainsi, deux cordes
ayant exactement une extrémité en commun auront des couleurs diérentes.

12
 Pour chaque couleur c, on considère le graphe Gc dont les sommets sont les cordes de couleur
c, et dont deux sommets sont reliés par une arête s'ils correspondent à des cordes qui ne sont pas
disjointes. Le but est de montrer qu'il existe une couleur c telle que Gc contienne un ensemble de
100 sommets indépendants. Pour cela, nousPallons utiliser le résultat de l'exercice 12, en montrant
que la moyenne des quantités f (Gc ) = v∈Gc 1+d(v) 1
sur tous les graphes Gc est strictement
supérieure à 100.
Chaque corde ` divise le cercle en deux arcs, et par le principe des tiroirs l'un des deux
arcs contient un nombre m(`) de points inférieur ou égal à n − 1 en son intérieur. Pour tout
i = 0, 1 . . . , n − 2, il y 2n cordes ` avec m(`) = i. Une telle corde a un degré inférieur ou égal à i
dans le graphe Gc correspondant à sa couleur c : en eet, les cordes de couleur c qu'elle intersecte
doivent nécessairement avoir une extrémité parmi les i points du  petit arc qu'elle intercepte,
et deux cordes de même couleur ont des extrémités distinctes.
D'après ce que nous venons de voir, pour tout i ∈ {0, . . . , nP− 2}, les 2n cordes ` telles que
m(`) = i contribuent au moins avec un terme 1+i 2n
à la somme c f (Gc ). Il y a 4n − 3 couleurs
en tout, donc en prenant la moyenne sur toutes les couleurs, cela donne qu'il existe une couleur c
telle que
n−1 n−1
2n X 1 1X1
f (Gc ) ≥ > .
4n − 3 i=1 i 2 i=1 i

Il reste donc à montrer que > 200 pour n = 499. Or

Pn−1 1
i=1 i

n−1 499 k
2
X 1 X X 1
= 1+
i=1
i k=1
i
i=2k−1 +1
499 k−1
X 2
> 1+
k=1
2k
499
= 1+ > 200,
2
ce qui conclut.

13