# Les problèmes de coloration en théorie des graphes

Claude Berge

► To cite this version:

Claude Berge. Les problèmes de coloration en théorie des graphes. Annales de l'ISUP, 1960, IX (2), pp.123-160. hal-04092789

HAL Id: hal-04092789

https://hal.science/hal-04092789

Submitted on 9 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# LES PROBLÈMES DE COLORATION EN THÉORIE DES GRAPHERES

Claude BERGE

Maître de Recherches au C.N.R.S.

## INTRODUCTION

Le problème de la coloration des graphes s'est révélé récemment être à la base de nombreux problèmes combinatoires connus ; on peut également y ramener certains problèmes classiques de la statistique mathématique : celui de la transformation d'un rectangle latin en carré latin (cf. [1], p. 94), celui de la répartition des triades en "promenades" (cf. [1], p. 36), etc. Le présent article a pour but d'étudier certains développements modernes, des théorèmes trop récents pour avoir pu être inclus dans [1], et surtout d'améliorer leurs démonstrations. L'outil principal est la notion de "graphe critique" (1) ; ce qui sera dit ici des graphes "gallaïens" et "pseudo-gallaïens" n'a peut être pas un caractère définitif, et les conjectures que nous indiquons ici semblent devoir susciter des recherches ultérieures.

## I - GRAPHERES CRITIQUES.

Soit $G$ un graphe (non orienté) fini et sans boucles. On désignera l'ensemble de ses sommets par $X$, l'ensemble de ses arêtes par $U$, l'ensemble des sommets adjacents à $x_0$ par $\Gamma x_0$, le degré du sommet $x_0$ par $d(x_0) = |\Gamma x_0|$. Si un graphe est désigné par $G'$ ou $G''$, on désignera le degré de $x_0$ dans ces graphes par $d'(x_0)$ ou $d''(x_0)$. Un ensemble $S \subset X$ est dit *stable* si deux quelconques de ses points sont non-adjacents ; un ensemble $C \subset X$ est un *clique* si deux quelconques des sommets de $C$ sont adjacents ; un ensemble $A \subset X$ est un *ensemble d'articulation* si $G$ est connexe, et si le sous-graphe engendré par $X-A$ ne l'est pas ; le

<footnote>(1) en anglais : "node-critical graph". Cette notion est plus générale que celle de "critical graph" utilisée dans les articles de Dirac par exemple : en effet, comme nous adoptons la terminologie de [1], un "sous-graphe" consiste ici en un sous-ensemble de sommets avec *toutes* les arêtes qui relient deux sommets du sous-ensemble.</footnote>
sous-graphe engendré par X-A admet alors au moins deux composantes connexes disjointes $B_1$ et $B_2$, et les sous-graphes connexes engendrés par $B_1 \cup A$ ou $B_2 \cup A$ sont appelés des **pièces** (relativement à l'ensemble d'articulation A).

Si $p$ est un entier $> 0$, on dit que le graphe $G$ est **p-chromatique** s'il est possible de colorier les sommets avec $p$ couleurs distinctes de sorte que deux sommets adjacents ne soient pas de même couleur. On assimile souvent les couleurs à des entiers $1, 2, \dots, p$, et une **coloration** est une fonction $g$, appliquant $X$ dans $\{1, 2, \dots, p\}$, et telle que :

$$ (x, y) \in U \implies g(y) \neq g(x) $$

Le **nombre chromatique** du graphe $G$ est la plus petite valeur de $p$ pour lequel le graphe est **p-chromatique** ; on le désigne toujours par $\gamma(G)$. Un graphe $G$ est dit **k-critique** (ou **k-minimal**), si $\gamma(G) = k$, et si pour tout sommet $x_o$, le sous-graphe $G_o$ engendré par $X - \{x_o\}$ a un nombre chromatique $\gamma(G_o) < k$.

Remarquons que dans ce cas, on a nécessairement $\gamma(G_o) = k-1$ ; en effet, si $\gamma(G_o) < k-1$, on pourrait colorier $G_o$ avec $k-2$ couleurs et le sommet $x_o$ avec une $(k-1)$-ème couleur, ce qui impliquerait $\gamma(G) \le k-1$.

Nous nous proposons maintenant d'étudier les principales propriétés des graphes $k$-critiques.

**Propriété 1** - Dans tout graphe $G$ avec $\gamma(G) = k$, il existe un sous-graphe $k$-critique.

En effet, si $G$ n'est pas $k$-critique, il existe un sommet $x_o$ dont la suppression ne diminue pas le nombre chromatique de $G$ ; si le sous-graphe $G_o$ engendré par $X - \{x_o\}$ n'est pas $k$-critique, il existe un sommet $x_1$ dont la suppression ne diminue pas le nombre chromatique de $G_o$, etc. Tôt ou tard, on obtiendra donc un graphe $G_q$ qui est $k$-chromatique.

**Propriété 2** - Dans un graphe $k$-critique, le degré de chaque sommet $x$ vérifie :

$$ d(x) \ge k-1 $$

En effet, si $d(x_o) < k-1$, on pourrait colorier avec $(k-1)$ couleurs le sous-graphe $G_o$ engendré par $X - \{x_o\}$ ; comme dans $\Gamma_{x_o}$ ne peut figurer $k-1$ couleurs distinctes, on pourra ainsi colorier $x_o$ avec une des $(k-1)$ couleurs, ce qui contredit $\gamma(G) = k$.
**Propriété 3** - *Un graphe k-critique est connexe. (évident).*

**Propriété 4** - *Un graphe k-critique n'admet pas une clique pour ensemble d'articulation.*

Soit C une clique qui serait aussi un ensemble d'articulation. Comme G est k-critique, le nombre d'éléments de cette clique est :

$$|C| = \gamma(C) \leq k-1$$

Soient $B_1, B_2, B_3, ...$ les composantes du sous-graphe engendré par X-C, et soient $B'_1 = B_1 \cup C, B'_2 = B_2 \cup C, ...$ les pièces correspondantes. Comme G est k-critique, on peut colorier chaque pièce avec k-1 couleurs, donc on peut colorier G avec k-1 couleurs, ce qui contredit $\gamma(G) = k$.

**Propriété 5** - *Un graphe k-critique n'admet pas un point d'articulation (c'est-à-dire : un sommet dont la suppression disconnecte le graphe).*

Ceci est un cas particulier de la propriété précédente.

**Propriété 6** - *Si G est k-critique et si $A = \{a, b\}$ est un ensemble d'articulation de deux éléments, il y a exactement deux pièces $B'_1$ et $B'_2$ relatives à cet ensemble d'articulation, et l'on a :*

$$\gamma(B'_1) = \gamma(B'_2) = k-1$$

En effet, une pièce B' relative à A peut être coloriée avec k-1 couleurs, et l'on a trois possibilités :

(1) - on ne peut pas colorier B' en k-1 couleurs de sorte que a et b soient de même couleur ;

(2) - on ne peut pas colorier B' en k-1 couleurs de sorte que a et b soient de différentes couleurs ;

(3) - il existe un coloriage de B' en k-1 couleurs avec a et b de même couleur, et un autre avec a et b de différentes couleurs.

Une pièce B' appartient nécessairement à l'un des types (1) ou (2) (car sans cela on pourrait supprimer la composante B correspondante sans changer le nombre chromatique de G) ; si B' appartient au type (1), on a $\gamma(B') = k-1$, car si $\gamma(B') = k-2$, on peut colorier a et b avec un (k-1)-ème couleur, ce qui contredit que B' appartient au type (1). Pour la même raison, si B' appartient au type (2), on a $\gamma(B') = k-1$.

Comme $\gamma(G) = k$, il y a nécessairement une pièce du type (1) et une pièce du type (2) ; comme G est critique, il y a seulement une pièce de chaque type.
**Propriété 7** - Si G est k-critique, (avec k ≥ 4), et si A = {a, b, c} est un ensemble d'articulation de trois éléments :

1. - s'il y a une arête dans A : cet ensemble d'articulation admet au plus 3 pièces, et celles-ci sont de nombre chromatique k-1 ;

2. - s'il y a deux arêtes dans A : cet ensemble d'articulation admet au plus deux pièces, et celles-ci sont de nombre chromatique k-1 ;

3. - s'il y a trois arêtes dans A : absurde, en vertu de la propriété 4 ;

4. - s'il n'y a pas d'arêtes dans A : cet ensemble d'articulation admet au plus 5 pièces, dont les nombres chromatiques sont k-2 ou k-1.

Démontrons par exemple le premier cas, et supposons que a et b sont les deux sommets reliés de A : si l'on colorie une pièce B' avec k-1 > 3 couleurs, les sommets a, b, c, peuvent être coloriés : 121, 122 ou 123. Une pièce B' ne peut admettre à la fois ces trois types de coloration (car G critique), donc γ(B') = k-1 (car si γ(B') < k-2, on pourrait à l'aide d'un (k-1)-ème couleur obtenir n'importe laquelle des trois types de coloration).

<figure><img src="image_2.png" /><figcaption>(2 pièces)</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(3 pièces max.)</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(2 pièces)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(5 pièces max.)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(3 pièces max.)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(2 pièces)</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(5 pièces max.)</figcaption></figure>

**Figure 1** - Quelques ensembles d'articulations avec le nombre maximum de pièces qu'ils comportent.
Si une pièce $B_1^1$ admet deux types de coloration, il existe une pièce $B_2^1$ qui n'admet que le troisième type de coloration (et il n'y a que ces deux pièces puisque G est critique).

Si aucune pièce n'admet deux types de coloration, il peut exister trois pièces $B_1^1, B_2^1, B_3^1$, admettant respectivement les trois types de coloration.

**Propriété 8** - Soit G un graphe k-critique, et $i(G)$ son indice de cohérence, c'est-à-dire le nombre minimum d'arêtes qu'il faut supprimer pour disconnecter le graphe ; on a :

$$i(G) \geq k-1$$

Soient $X_0$ et $Y_0$ deux ensembles disjoints des sommets, avec :

$$X_0 \neq \emptyset ; Y_0 \neq \emptyset \\ X_0 \cap Y_0 = \emptyset ; X_0 \cup Y_0 = X$$

Soient $a_1, a_2, \dots, a_r$ les sommets de $X_0$ reliés à $Y_0$, et posons :

$$\Gamma_{a_i} \cap Y_0 = \{ b_1^1, b_1^2, \dots \} = A_i$$

Nous allons supposer que le nombre d'arêtes reliant $X_0$ et $Y_0$ est $<k-1$ (preuve par l'absurde), c'est-à-dire que :

$$\sum_{i=1}^{r} |A_i| \leq k-2$$

Comme G est k-critique, il existe pour $X_0$ une coloration g en (k-1) couleurs, et, quitte à renuméroter les couleurs, on peut supposer que :

$$g(a_i) < i \quad (i = 1, 2, \dots, r)$$

Il existe pour $Y_0$ une coloration h en (k-1) couleurs, et on peut s'arranger pour que sur $A_1$, cette coloration h vérifie :

$$1/ - h(b_1^1) = 2 ; \text{ quitte à permuter les couleurs 2 et h(b_1^1)} ;$$

$$2/ - h(b_2^1) \leq 3 \text{ et } \neq 1 ; \text{ quitte dans le cas contraire à permuter les couleurs 3 et h(b_2^1)} ;$$

$$3/ - h(b_3^1) \leq 4 \text{ et } \neq 1 ; \text{ quitte dans le cas contraire à permuter les couleurs 4 et h(b_3^1)} ; \text{ etc.}$$
De cette façon, les couleurs de $A_1$ seront comprises entre 2 et $\alpha_1$, où :

$$ \alpha_1 > 1, \quad \alpha_1 \le |A_1| + 1 $$

On peut s'arranger de la même façon pour que les couleurs de $A_1$ soient comprises entre $\alpha_1 + 1$ et $\alpha_2$, où :

$$ \alpha_2 > 2; \quad \alpha_2 \le |A_1| + 1 + |A_2| $$

Et ainsi de suite, jusqu'à ce que les couleurs de $A_r$ soient comprises entre $\alpha_{r-1} + 1$ et $\alpha_r$, où :

$$ \alpha_r > r; \quad \alpha_r \le \sum_{i=1}^{r} |A_i| + 1 \le (k-2) + 1 = k-1 $$

La coloration égale à $g(x)$ si $x \in X_o$ et à $h(y)$ si $y \in Y_o$ sera alors une coloration du graphe $G$, car :

$$ g(a_i) \le i; \quad \alpha_{i-1} + 1 > (i-1) + 1 = i $$

$G$ étant colorié en $(k-1)$ couleurs, ceci contredit $\gamma(G) = k$.

**Propriété 9** - Si $S$ est un ensemble stable maximal d'un graphe $G$ k-criktique, et si $G'$ est le sous-graphe engendré par $X-S$, alors on a :

$$ d'(x) < d(x) \quad (x \in X-S) \qquad (1) $$

$$ \gamma(G') = k-1 \qquad (2) $$

On a (1), car tout sommet $x \notin S$ est relié à $S$ (sans cela $S$ ne serait pas maximal).

On a (2), car $\gamma(G') \le \gamma(G) - 1 = k-1$, et si $\gamma(G') < k-1$, on pourrait manifestement colorier $G$ avec seulement $k-1$ couleurs.

## II - COLORATION D'UN GRAPHE SANS CLIQUES DE $\gamma(G)$ ELEMENTS

Proposons-nous d'abord d'étudier le nombre chromatique d'un graphe d'après les degrés de ses sommets.

**Théorème de KEMPE** - Si $G$ est un graphe connexe, $x_o$ un de ses sommets, et si

$$ d(x) \le q \quad (x \ne x_o) , $$
alors il existe une coloration $g$ telle que :

$$g(x) \le q \quad (x \neq x_o)$$

Considérons tout d'abord une coloration quelconque $g$, et, quitte à diminuer successivement pour tout sommet $x$ la valeur de $g(x)$, on peut supposer que $g(x)$ est le plus petit nombre ne figurant pas dans $\{g(y)/y \in \Gamma x\}$. On a alors :

$$g(x) \le q + 1 \quad (x \neq x_o)$$

Si $x_1$ est un sommet adjacent à $x_o$, montrons qu'il est possible de trouver une coloration $g'$ telle que :

$$g'(x) = g(x) \quad (x \neq x_o, x_1)$$

$$g'(x_1) \le q$$

Si $g(x_1) \le q$, ceci est démontré ; si $g(x_1) = q + 1$, $g(y)$ prend toutes les valeurs $1, 2, \dots, q$ quand y parcourt les q sommets adjacents à $x_1$-donc :

$$g(x_o) = \alpha \le q$$

Posons :

$$g'(x_1) = \alpha$$

$$g'(x) = g(x) \quad (x \neq x_o, x_1)$$

$$g'(x_o) = \text{le plus petit entier qui ne figure pas dans } \\ \text{l'ensemble } \{g'(y)/y \in \Gamma x_o\}.$$

Cette fonction $g'$ est bien une coloration et répond aux conditions proposées.

Tout sommet $y \neq x_o$ et de couleur $q+1$ est relié à $x_o$ par une chaine $\mu = [x_0, x_1, x_2, \dots, x_p = y]$ (car $G$ est connexe) ; comme il a été indiqué, on peut faire passer la couleur $q+1$ de $x_p$ à $x_{p-1}$, puis de $x_{p-1}$ à $x_{p-2}$, etc. jusqu'en $x_o$. Ainsi, en ne modifiant que la coloration des sommets de la chaine $\mu$, on a pu "drainer" la couleur $q+1$ jusqu'en $x_o$.

En répétant cette opération de drainage pour d'autres sommets $y$ de couleur $q+1$, on obtiendra bien la coloration cherchée.
**Théorème de R.L. BROOKS** - Un graphe G dont le degré maximum est $\max_{x \in X} d(x) = q$ peut être colorié en q couleurs, excepté dans les cas suivants:

(1) - si $q = 2$ : une des composantes du graphe est un cycle élémentaire de longueur impaire ;

(2) - si $q = 2$ : une des composantes du graphe est un clique de $q+1$ éléments.

Si $q = 1$ ou $q = 2$, le théorème est évident ; supposons $q > 2$.

Supposons le théorème vrai pour tout graphe de moins de n sommets, et montrons qu'il est vrai pour un graphe donné G de n sommets (sans cliques de $q+1$ éléments).

En effet, dans le cas contraire, on a $\gamma(G) \ge q+1$ ; comme $\gamma(G) \le q+1$ d'après le théorème de Kempe, on a $\gamma(G) = q+1$, et le graphe G est même $(q+1)$-critique. D'après la propriété 2, on a alors :

$$d(x) = q \quad (x \in X)$$

G est aussi connexe et sans points d'articulation (Propriété 3 et 5).

1/ - Le graphe G n'étant pas une clique de $q+1$ éléments, il existe deux sommets $x_0$ et $x_1$ non adjacents, et au sommet $x_0$ on fait correspondre une coloration g comme au théorème de Kempe, avec :

$$g(x_0) = q+1$$

$$g(x) \le q \quad (x \neq x_0)$$

Comme $d(x_1) = q$, $g(x_1) \le q$, et $\max_{y \in \Gamma_{x_1}} g(y) \le q$, il y a dans $\Gamma_{x_1}$ deux sommets a et b de même couleur.

2/ - A = {a, b} est un ensemble d'articulation entre $x_0$ et $x_1$; en effet, dans le cas contraire, il existe une chaine $\mu[x_0, x_1]$ allant de $x_1$ à $x_1$ sans passer par A ; on pourrait alors drainer la couleur $q+1$ de $x_0$ à $x_1$ le long de cette chaine, (cf. Théorème de Kempe), et comme $x_1$ est toujours adjacent à deux sommets a et b de même couleur, on pourra complètement éliminer la couleur $q+1$. Ce qui est absurde, puisque $\gamma(G) = q+1$.

Joignons a et b, et considérons les deux pièces $B'_0$ et $B'_1$ relatives à l'ensemble d'articulation A, avec $x_0 \in B'_0$, $x_1 \in B'_1$. Comme ni a ni b ne sont des points d'articulation du graphe G, les degrés de a dans les deux graphes $B'_0$ et $B'_1$ vérifient :

$$d_0(a) \ge 2 \quad d_1(a) \ge 2$$
d'où :

$$d_o(a) \le q, d_1(a) \le q$$

De même :

$$d_o(b) \le q, d_1(b) \le q$$

3/ - $B'_o$ ou $B'_1$ est une clique de $q+1$ éléments (car sinon, on pourrait les colorier en $q$ couleurs par hypothèse, d'où $\gamma(G) = q$). Soit $B'_o$ la clique, par exemple; on a :

$$d_o(a) = q \quad d_o(b) = q \quad d_1(a) = 2 \quad d_1(b) = 2$$

4/ - Soient $G_o$ et $G_1$ les graphes obtenus à partir de $B'_o$ et $B'_1$ en rétrécissant l'arête $[a, b]$ - c'est-à-dire en identifiant les sommets $a$ et $b$ à un sommet unique. -

$G_o$ est coloriable en $q$ couleurs, puisque c'est une clique de $q$ éléments.

$G_1$ également, car $d_1(a) = 2 < q$, et en vertu du théorème de Kempe, un graphe de degré maximum $q$ avec un sommet de degré $< q$ peut être coloré en $q$ couleurs.

Donc $G$ est coloriable en $q$ couleurs, ce qui est absurde.

**Corollaire 1** - Si $S = \{x/d(x) > q\}$ est un ensemble stable ($q>3$), et si $Y-S$ ne contient pas une clique de $q$ sommets, alors $G$ est coloriable en $q$ couleurs.

En effet, soit $G'$ le graphe déduit de $G$ en retranchant un ensemble stable maximal $\bar{S}$ contenant $S$. On a :

$$d'(x) \le d(x) - 1 \le q - 1 \quad (x \in G')$$

Comme $G'$ ne contient pas de clique de $q$ sommets, $G'$ est coloriable en $q-1$ couleurs d'après le théorème de BROOKS, d'où :

$$\gamma(G) \le \gamma(G') + 1 \le q$$
**Corollaire 2** - Si le sous-graphe engendré par $S = \{x/d(x) > q\}$ est k-chromatique ($q > 3$, $k = 1, 2, \dots, q-3$), considérons deux cas :

(1) - Si X-S contient une clique de ($q - k + 1$) éléments, alors le graphe G est coloriable en $q+1$ couleurs ;

(2) - Si X-S ne contient pas de clique de ($q - k + 1$) éléments, alors le graphe G est coloriable en q couleurs.

Démontrons (2): soient $1, 2, \dots, k$ les couleurs de S ; retranchons un ensemble stable maximal contenant tous les sommets de couleur 1 ; puis un ensemble stable maximal contenant tous les sommets de couleur 2 restant, etc., jusqu'à ce qu'on épuise les k couleurs de S. Le nouveau graphe G' obtenu vérifie :

$$d'(x) \le q - k \ ; \ (x \in G')$$

G' est coloriable en q-k couleurs (d'après le théorème de BROOKS) et l'on a bien :

$$\gamma(G) \le \gamma(G') + k \le (q-k) + k = q$$

(1) se démontre de la même façon - en utilisant le théorème de KEMPE au lieu du théorème de BROOKS.

**Lemme** - Soit G un graphe ($q + 1$) - critique contenant une clique $C = \{c_1, c_2, \dots, c_q\}$ de q éléments, avec :

$$\sum_{i=1}^{q} [d(c_i) - q] \le q - 3$$

Alors, dans tout coloriage de X-C en q couleurs, les ensembles $A_1 = \Gamma c_1 - C$ contiendront une couleur commune.

Supposons :

$$d(c_1) \le d(c_2) \le \dots \le d(c_q)$$

Comme G est ($q+1$) - critique, on a $d(c_1) \ge q$ ; comme $d(c_i)-q > 1$ pour au plus $q-3$ des $c_i$, on a :

$$d(c_1) = d(c_2) = d(c_3) = q$$

Ainsi, $|A_1| = 1$, et désignons par 1 la couleur du sommet unique de $A_1$ dans un coloriage de X-C en q couleurs. Supposons qu'il existe un ensemble $A_{1o}$ ne contenant pas cette couleur 1.

Nous allons montrer que ceci est absurde, c'est-à-dire que l'on
peut colorier la clique C avec les q couleurs déjà utilisées de X-C sans que deux sommets adjacents de G n'aient la même couleur (ce qui contredirait $\gamma(G) = q+1$).

Le coloriage g se fera de proche en proche de la façon suivante :

- on prend $g(c_{i_0}) = 1$;

- si $q \neq i_0$: on prend $g(c_q) \neq g(c_{i_0})$ et des couleurs de $A_q$:

- si $q-1 \neq i_0$: on prend $g(c_{q-1}) \neq g(c_{i_0})$, $g(c_q)$, et des couleurs de $A_{q-1}$; etc.

Remarquons que :

$$ \sum_{i=j}^{q} [d(c_i) - q] = \sum_{i=j}^{q} (|A_i| - 1) \le q - 3 $$

$$ \text{donc :} \qquad (q - j + 1) (|A_j| - 1) \le q - 3 $$

$$ \text{où :} \qquad |A_j| \le \frac{q-3}{q-j+1} + 1 $$

Le coloriage préconisé pour $c_j$ sera certainement possible tant que l'ensemble $A_j \cup \{c_{i_0}, c_q, c_{q-1}, \dots, c_{j+1}\}$ a moins de q éléments, c'est-à-dire :

$$ \frac{q-3}{q-j+1} + 1 + (q-j+1) \le q-1 $$

$$ -j+3 + \frac{q-3}{q-j+1} \le 0 $$

$$ j^2 - (q+4)j + 4q \le 0 $$

Les racines du binôme sont $j' = 4$ et $j'' = q$, on pourra colorier $c_j$ si :

$$ 4 \le j \le q $$

Il reste à vérifier les cas $j = 2$ et $j = 3$ ; comme $d(c_2) = d(c_3) = q$, les ensembles $A_2$ et $A_3$ n'ont qu'un seul élément $a_2$ et $a_3$; si $i_0 \neq 2$, on peut prendre :

$$ g(c_2) \neq g(c_4), g(c_5), \dots, g(c_q) \text{ et de } g(c_{i_0}) = g(a_2) = 1 $$

Si en $i_0 \neq 3$, on peut prendre :
$$g(c_3) \neq g(c_4), \dots, g(c_q), g(c_2) \text{ et de } g(c_{1o}) = g(a_3) = 1$$

De toutes façons, on aura colorié G avec q couleurs C.Q.F.D.

**Théorème de G.A. DIRAC** - Si G est un graphe de nombre chromatique $\gamma(G) = q + 1$, sans cliques de $q + 1$ éléments, et si l'on pose $S = \{x/d(x) > q\}$, alors on a :

$$\sum_{x \in S} [d(x) - q] \geq q - 2$$

Si $q = 1$, le théorème est creux, car on ne peut avoir à la fois $\gamma(G) = 2$ et pas de cliques de deux sommets.

Si $q = 2$, on a nécessairement :

$$\sum_{x \in S} [d(x) - q] \geq 0 = q - 2$$

Si $q = 3$, le théorème est évident, car $S \neq \emptyset$ (d'après le théorème de BROOKS), donc :

$$\sum_{x \in S} [d(x) - q] > 1 = q - 2$$

Supposons le théorème vrai pour tous les graphes de nombre chromatique inférieur à $q + 1$, et proposons nous de le démontrer pour un graphe G donné, de nombre chromatique $\gamma(G) = q + 1$, avec $q > 3$. (D'après le théorème de BROOKS, on sait déjà que $S \neq \emptyset$). Supposons (preuve par l'absurde) que G n'ait pas de cliques de $q + 1$ éléments et vérifie cependant :

$$\sum_{x \in S} [d(x) - q] < q - 2$$

Supposons que G soit $(q + 1)$-critique (car sans cela on peut le remplacer par un sous-graphe $(q + 1)$-critique, et celui-ci aurait nécessairement les mêmes propriétés). Comme dans G on a $d(x) \geq q$ pour tout sommet $x \in X$, on a donc :

$$\sum_{x \in X} [d(x) - q] < q - 2 \quad (1)$$

Nous allons examiner successivement les deux cas suivants, et démontrer qu'ils aboutissent tous deux à une absurdité.

**_1er cas_** - G n'admet pas de cliques de $q$ éléments.

Soit $x_o$ un sommet de S (il en existe au moins un, d'après le théorème de BROOKS).
rème de BROOKS) ; soit T un ensemble stable maximal contenant $x_0$ (c'est-à-dire construit en commençant par le sommet $x_0$) ; soit $G'$ le sous-graphe engendré par $X-T$. On a, d'après la propriété 5 :

$$ \gamma(G') = \gamma(G) - 1 = (q+1) - 1 = q $$

Comme $d(x) \ge d'(x)+1$ pour tout $x \in X-T$ (propriété 5) l'ensemble $S' = \{x/x \in X-T, d'(x) > q-1\}$ est contenu dans l'ensemble $S = \{x/x \in X, d(x) > q\}$, et l'inclusion est même stricte, car $x_0 \in S$ et $x_0 \notin S'$. On a donc :

$$ \begin{aligned} \sum_{x \in S'} [d'(x) - (q-1)] &\le \sum_{x \in S'} [d'(x) + 1 - q] \le \sum_{S'} [d(x) - q] \\ &\le \sum_{S} [d(x) - q] - 1 < (q-1) - 2 \end{aligned} $$

D'autre part, comme $G'$ n'a pas de clique de $q$ éléments, et comme le théorème est supposé vrai pour les graphes de nombre chromatique $\le q$, on a aussi :

$$ \sum_{x \in S'} [d'(x) - (q-1)] \ge (q-1) - 2 $$

D'où la contradiction cherchée.

### 2ème cas - G admet une clique de $q$ éléments.

Soit $C = \{c_1, c_2, \dots, c_q\}$ cette clique.

L'ensemble $A_i = \Gamma c_i - C$ est non-vide (car $d(c_i) \ge q$, puisque $G$ est $(q+1)$-critique).

L'ensemble $A = \Gamma C - C$ a au moins deux éléments (car $G$ n'a pas de clique de $q+1$ éléments).

Quitte à renuméroter les sommets, supposons :

$$ d(c_1) \le d(c_2) \le \dots \le d(c_q) $$

Comme, d'après (1), $G$ contient moins de $q$ sommets de degré $> q$, on a :

$$ d(c_1) = q $$

Soit donc $a_1$ le sommet unique de $A_1 = \Gamma c_1 - C$. Comme $G$ n'a pas de clique de $(q+1)$ éléments, il existe un sommet $c_j$ non relié à $a_1$, et prenons pour $j$ l'indice le plus petit possible.
<figure><img src="image_9.png" /><figcaption>Fig. 2.</figcaption></figure>

Posons : $A_j = \{b_1, b_2, \dots\}$.

Dans le sous-graphe engendré par X-C, si l'on joint le sommet $a_1$ aux sommets $b_1, b_2, \dots$, on obtient un graphe $G'$. Comme X-C est coloriable en q couleurs ($G$ est $(q+1)$-critique), le graphe $G' - \{a_1\}$ est coloriable en q couleurs, donc $\gamma(G') \le q + 1$.

D'autre part, d'après le lemme 3, $G'$ n'est pas coloriable en q couleurs, d'où :

$$ \gamma(G') = q + 1 $$

Soit $G''$ le sous-graphe $(q+1)$ critique qu'il contient, et soit $G'''$ le graphe déduit de $G''$ en retirant les arêtes auxiliaires du type $[a_1, b_i]$.

$G'''$ contient le sommet $a_1$ et un des sommets de $A_j$ (car si $G''$ ne contenait pas une arête du type $[a_1, b_i]$, on aurait $\gamma(G'') \le q$).

Notons que l'on a :

$$ d(a_1) \ge d''(a_1) - |A_j| + (j-1) \ge q - |A_j| - 1 + j $$

On en déduit immédiatement que $|A_j| = 1$, car si $|A_j| \ge 2$, on pourrait écrire :

$$ \begin{aligned} \sum_x [d(x)-q] &\ge \sum_{i=j}^q [d(c_i)-q] + [d(a_1)-q] \ge (q-j+1) [|A_j|-1] + [-|A_j|-1+j] \\ &= (q-j+1) [|A_j|-1] - [|A_j|-1] + j - 2 \\ &= (q-j) [|A_j|-1] + j - 2 > (q-j) + j - 2 = q - 2 \end{aligned} $$

(ce qui contredirait (1)).
Soit donc b le sommet unique de $A_j$ ; le graphe $G'''$ est déduit du
graphe $(q+1)$-critique $G''$ par suppression de la seule arête $[a_1, b]$. Donc :

$$
d'''(a_1) = d''(a_1) - 1 \geq q - 1
$$

$$
d'''(b) = d''(b) - 1 \geq q - 1
$$

$$
d'''(x) \geq q \quad (x \in X''', x \neq a_1, b)
$$

En vertu de ceci, et en vertu de la propriété 8, on peut écrire :

$$
\sum_x [d(x) - q] \ge \sum_{x'''} [d(x) - q] = \sum_{x'''} [d'''(x) - q] + \text{(nombre}
$$

$$
d'\text{arêtes joignant } X''' \text{ à } X-X''') \geq -2+(q)=q-2
$$

On a donc la contradiction cherchée avec (1).

Corollaire - si G est (q+1)-critique sans clique de (q+1) éléments,
alors le nombre n de sommets et le nombre m des arêtes vérifient :

$$
2m \geq (n+1)q - 2
$$

En effet, comme $d(x) \ge q$ pour tout sommet $x$, on a :

$$
2m = \sum_{x \in S} d(x) + [n - |S|]q \ge q - 2 + |S|q + nq - |S|q = (n+1)q - 2
$$

Remarque.

Il est facile de voir que les inégalités du théorème et de son corol-
laire sont les meilleurs possibles pour $q \ge 3$ ; construisons en effet un
graphe $G$, avec $\gamma(G) = q+1$, et pour lequel on ait l'égalité. Considérons
deux cliques $C = \{c_1, c_2, \dots, c_{q+1}\}$ et $D = \{c_1, d_2, \dots, d_{q+1}\}$, et formons $G$
en retranchant les arêtes $[c_1, c_2]$, $[c_1, d_{q+1}]$, et en ajoutant l'arête
$[c_2, d_{q+1}]$.

<figure><img src="image_10.png" /><figcaption>Figure 3.</figcaption></figure>
$\gamma(G) = q+1$, et G ne contient pas de cliques de $(q+1)$ éléments;
en outre, le seul sommet de G est $c_1$, avec :

$$d(c_1) = 2q - 2$$

$$\text{Donc :} \qquad \sum_{x \in S} [d(x) - q] = d(c_1) - q = q - 2$$

### III - NOMBRE $\omega(G)$ ASSOCIÉ AU GRAPHE G.

On désigne par $\omega(G)$ le nombre maximum d'éléments d'une clique du graphe G. On a toujours :

$$\gamma(G) \ge \omega(G)$$

Il s'agit ici de déterminer certaines catégories de graphes pour lesquels on a nécessairement $\gamma(G) = \omega(G)$.

Notons tout d'abord :

**Théorème 1** - Soit G un graphe avec $\omega(G) = k$ ; posons $S = \{x / d(x) > k\}$ ;
si l'on a :

$$\sum_{x \in S} [d(x) - k] < k - 2,$$

$$\text{alors on a} \qquad \gamma(G) = \omega(G)$$

En effet, on a $\gamma(G) \ge k$ ; si $\gamma(G) > k$, il existe un sous-graphe $G'$ de G avec $\gamma(G') = k + 1$.

$G'$ n'ayant pas de clique de $(k+1)$ éléments, le théorème de Dirac montre que :

$$\sum_{\substack{x \in G' \\ x \in S'}} [d'(x) - k] \ge k - 2$$

Comme ceci contredit notre hypothèse, on a bien $\gamma(G) = k$.

Nous disons qu'un graphe $G = (X, U)$ est **k-complet** si $\omega(G) = k$, et si l'adjonction d'une arête quelconque (n'appartenant pas déjà à $U$) augmente $\omega(G)$ ; une clique de $k$ sommets constitue un graphe $k$-complet.

Si $G$ est un graphe avec $\omega(G) = k$, on peut toujours trouver un graphe $k$-complet $G_0$ ayant les mêmes sommets que $G$, et dont l'ensemble des arêtes contient l'ensemble des arêtes de $G$ ; on dira alors que $G$ est **plongé** dans le graphe $k$-complet $G_0$.
Si G est un graphe quelconque avec $\omega(G) = k$, et si $\omega(G) = \gamma(G)$, il peut être plongé dans un graphe k-complet $G_o$ avec $\gamma(G_o) = \omega(G_o)$ ; inversement, si un graphe G peut être plongé dans un tel graphe $G_o$, on a :

$$k = \omega(G) \leq \gamma(G) \leq \gamma(G_o) = k$$

donc on a bien : $\omega(G) = \gamma(G)$

**Propriété 1** - Dans un graphe k-complet G, tout sommet x appartient à une clique C de k éléments ; l'ensemble $C - \{x\}$ sera appelé par la suite une "cellule de x".

Soit $a \in X$ ; si $\Gamma a \notin X$, soit $z \notin \Gamma a$ ; l'adjonction de l'arête $[a, z]$ créant une clique C de $k+1$ éléments, l'ensemble $C - \{a, z\}$, qui a $k-1$ éléments, est bien une cellule de a.

Si $\Gamma a = X$, il existe au moins deux sommets x et y non adjacents (car sans cela, G serait une clique de k éléments et le théorème serait démontré). Comme $G + [y, z]$ contient une clique C de $k+1$ éléments, et comme $a \in C$, l'ensemble $C - \{a, z\}$ est bien une cellule de a.

**Propriété 2** - Dans un graphe k-complet G, la condition nécessaire et suffisante pour que deux sommets a et b admettent une cellule commune est qu'ils soient non-adjacents.

1. Si a et b sont non adjacents, $G + [a, b]$ contient une clique C de $k+1$ éléments, donc $C - \{a, b\}$ est une cellule commune des sommets a et b.

2. Si a et b sont deux sommets adjacents, ils ne peuvent admettre une cellule commune C, car alors $C \cup \{a, b\}$ serait une clique de $(k+1)$ éléments.

**Propriété 3** - Dans un graphe k-complet G, les conditions suivantes sont équivalentes :

$$(1) - \gamma(G) = \omega(G);$$

(2) - G consiste en k ensembles stables reliés entre eux de toutes les façons possibles ;

(3) - Tout cycle élémentaire de longueur 5 admet au moins deux "cordes" (c'est-à-dire : arêtes reliant deux sommets non consécutifs du cycle).

(1) ⇒ (2), car si $\gamma(G) = k$, soient $S_1, S_2, \dots, S_k$ les k ensembles des sommets de même couleur. Ils sont stables ; en outre, si $x_1 \in S_1$,
$x_2 \in S_2$, on a $[x_1, x_2] \in U$, car sinon l'adjonction d'une nouvelle arête $[x_1, x_2]$ ne pourrait créer une clique de $(k+1)$ sommets (le nombre chromatique du nouveau graphe étant encore égal à $k$).

(2) $\Rightarrow$ (3) : soit $\mu = [x_1, x_2, x_3, x_4, x_5]$ un cycle de longueur 5, et soient $S_1, S_2, \dots, S_k$ les $k$ ensembles stables.

Si $k=1$ ou $k=2$, (3) est évident (car $\mu$ ne peut exister); si $k > 2$, le cycle $\mu$ rencontre successivement trois $S_i$ différents, soient par exemple : $S_1 \ni x_1$, $S_2 \ni x_2$, $S_3 \ni x_3$. Un des deux autres sommets $x_4$ ou $x_5$ appartient à $S_2$ (car sans cela $\mu$ admettrait deux cordes), soit : $x_4 \in S_2$. Mais alors $[x_1, x_4]$ et $[x_2, x_5]$ sont deux cordes de $\mu$: C.Q.F.D.

<figure><img src="image_11.png" /><figcaption>Fig. 4.</figcaption></figure>

(3) $\Rightarrow$ (1) : Montrons tout d'abord que si $a, x$ et $y$ sont trois sommets distincts avec $[a, x] \notin U$, $[a, y] \notin U$, alors on a $[x, y] \notin U$.

En effet, si $[x, y] \in U$, considérons une cellule C commune à $a$ et $x$ et une cellule C' commune à $a$ et $y$ (elles existent d'après la propriété 2).

On a $y \notin C$, car $[a, y] \notin U$ ; de même, $x \notin C'$.

C n'étant pas une cellule de $y$ (propriété 2), soit $z$ un sommet de $C$ non relié à $y$ ; de même, soit $z'$ un sommet de $C$ non relié à $x$.

<figure><img src="image_12.png" /><figcaption>Fig. 5.</figcaption></figure>
On a $z \neq z'$ (car l'un est relié à x, et l'autre ne l'est pas), donc le cycle $[x, y, z', a, z]$ est élémentaire et de longueur 5 : comme il ne peut admettre deux cordes, on a bien l'absurdité cherchée.

Ainsi, la relation binaire entre x et y définie par $[x,y] \notin U$ est une équivalence ; soient $S_1, S_2, \dots, S_p$ les classes d'équivalence. Comme le graphe est k-complet, on a $p = k$, et l'on peut donc colorier le graphe G avec k couleurs. Comme d'autre part $\gamma(G) \ge \omega(G) = k$, on a bien $\gamma(G) = k$.

**Théorème de ZARANKIEWICZ** - Dans un graphe G à n sommets, soit d la valeur minimum des degrés $d(x)$, et posons :

$$p = \text{partie entière par excès de } \left( \frac{n}{n-d} \right) \\ \text{alors } \omega(G) \ge p.$$

Remarquons tout d'abord que d'après la définition de $p$, on a :

$$\frac{n}{n-d} \le p < \frac{n}{n-d} - 1$$

On en déduit immédiatement :

$$\frac{p-2}{p-1} n < d \le \frac{p-1}{p} n \qquad (1)$$

Ceci dit, nous allons démontrer un théorème plus fort que l'énoncé de Zarankiewicz, à savoir : $\underline{si} \ d > \frac{p-2}{p-1} n$, toute clique de moins de $p$ éléments (et en particulier tout sommet) est contenue dans une clique de $p$ éléments.

Ceci est vrai pour $p = 2$, car alors $d > 0$, et tout sommet est l'extrémité d'au moins une arête. Supposons le théorème vrai pour $p$, et démontrons qu'il est encore vrai pour $p + 1$.

Considérons un graphe G, de n sommets, de degré minimum d, avec en outre :

$$d > \frac{(p+1)-2}{(p+1)-1} n = \frac{p-1}{p} n > \frac{p-2}{p-1} n$$
Donc, par hypothèse, une clique donnée $C_0$ de moins de $p$ éléments est contenue dans une clique $C = \{c_1, c_2, \dots, c_p\}$ avec exactement $p$ éléments. Il s'agit de montrer que :

$$ \bigcap_{i=1}^{p} (\Gamma c_i - C) \neq \emptyset $$

$$ \text{On a :} \qquad |\Gamma c_i - C| \ge d - (p-1) > \frac{p-1}{p} (n-p) $$

$$ \text{Donc : } |(X-C) - (\Gamma c_i - C)| = |X-C| - |\Gamma c_i - C| < (n-p) - \frac{p-1}{p} (n-p) = \frac{1}{p} |X-C| $$

$$ \text{On en conclut :} \qquad \bigcup_{i=1}^{b} [(X - C) - (\Gamma c_i - C)] \neq X - C $$

Or, en prenant le complémentaire par rapport à $X-C$ :

$$ \bigcap_{i=1}^{p} (\Gamma c_i - C) \neq \emptyset $$

Tout point $c_{p+1}$ qui appartient à cette intersection donne une clique $\{c_1, c_2, \dots, c_p, c_{p+1}\}$ qui contient la clique $C_0$ donnée. C. Q. F. D.

### Remarque

Montrons que ce théorème est le meilleur possible ; c'est-à-dire que si $n$ et $d$ sont deux entiers donnés, et si $p$ est la partie entière par excès de $(\frac{n}{n-d})$, il existe un graphe $G(n,p)$ à $n$ sommets, de degré minimum $d$, pour lequel on a exactement $\omega(G) = p$.

$n$ et $p$ étant donnés, définissons deux entiers $q$ et $r$ d'une façon unique par :

$$ n = pq + r \quad (0 < r \le p) $$

Prenons un ensemble $X$ de $n$ points, et divisons le en $p$ classes $X_1, X_2, \dots, X_p$, les $r$ premières classes étant de $(q + 1)$ sommets, les autres de $q$ sommets.

Formons un graphe $G$ en joignant deux points si et seulement si ils n'appartiennent pas à la même classe. On a évidemment $\omega(G) = p$. La valeur minimum des degrés de ce graphe est :

$$ \min d(x) = n - (q+1) = n - \frac{n}{p} + \frac{r}{p} - 1 $$
$$= \frac{p-1}{p} n + \left(\frac{r}{p} - 1\right) > \frac{p-1}{p} n - 1 \geq d - 1$$

Comme $\min d(x) > d - 1$, on a bien :

$$d(x) \geq d \quad (x \in X)$$

Le graphe $G$ ainsi construit est donc le graphe $G(n, p)$ cherché.

**Exemple** : Considérons 99 joueurs de bridge, et supposons que chacun n'accepte de jouer qu'avec 3 joueurs qu'il connait déjà. Combien chaque joueur doit-il connaitre de personnes pour qu'on soit assuré de former une table de bridge ?

Formons le graphe $G$ dont les sommets représentent les joueurs, et dont les arêtes lient les couples de joueurs se connaissant. Si chacun connait $d = 66$ joueurs, on peut avoir :

$$\omega(G) = \left\lfloor \frac{n}{n-d} \right\rfloor = \left\lfloor \frac{99}{33} \right\rfloor = 3$$

et il peut arriver qu'on ne trouve pas quatre joueurs pour un bridge. Au contraire, si chacun connait $k = 67$ autres joueurs, on est assuré de former une table de bridge ; bien plus, 3 joueurs arbitrairement donnés se connaissant peuvent trouver un quatrième.

**Théorème de TURÀN** - Soit $n$ et $p$ deux entiers $(2 \leq p \leq n)$; dans la famille $G^{(n,p)}$ des graphes $G$ d'ordre $n$ avec $\omega(G)=p$, le graphe $G(n,p)$ défini plus haut, et seulement lui, a le nombre maximum d'arêtes.

Considérons les différentes valeurs de $n$ par le tableau suivant :

$$ \begin{array}{lcccc} n = p+1 & 2p+1 & 3p+1 & \dots \\ p+2 & 2p+2 & 3p+2 & \dots \\ \cdot & \cdot & \cdot & \dots \\ \cdot & \cdot & \cdot & \dots \\ 2p & 3p & 4p & \dots \end{array} $$

Nous allons procéder par induction et montrer que si le théorème est vrai pour la colonne $q$, il est encore vrai pour la colonne $q+1$ ; c'est-à-dire, démontrons le pour un graphe $G$ d'ordre :

$$n_1 = p(q+1) + r_1 \quad (0 < r_1 \leq p)$$

Par hypothèse, $G$ est un graphe de $G^{(n_1, p)}$ avec le nombre maximum d'arêtes : comme $\omega(G)=p$, il contient une clique $C = \{c_1, c_2, \dots, c_p\}$ de $p$ éléments, et de tout sommet $x \notin C$, il part moins de $p$ arêtes vers
C (car sinon $\omega(G) = p + 1$).

Formons d'autre part un graphe $\bar{G} \in \mathcal{G}(n_1, p)$ en prenant un graphe $G(n_1 - p, p)$ et une clique $\bar{C} = \{\bar{c}_1, \bar{c}_2, \dots, \bar{c}_p\}$ de p éléments, puis en joignant tout élément de la classe $X_i$ dans $G(n_1 - p, p)$ à tous les $\bar{c}_j$ avec $j \neq i$.

Comme le graphe $G$ a par hypothèse au moins autant d'arêtes que $\bar{G}$, et que, en vertu de l'induction, le sous-graphe engendré par $X-C$ n'a pas plus d'arêtes que $G(n_1 - p, p)$, on a :

(1) - de tout $x \notin C$, il part exactement $p-1$ arêtes vers $C$;

(2) - le sous-graphe engendré par $X-C$ a exactement autant d'arêtes que $G(n_1 - p, p)$.

En vertu de (2) et de l'induction, le sous-graphe engendré par $X-C$ est effectivement un graphe $G(n_1 - p, p)$ et peut être divisé en classes $X_1, X_2, \dots, X_p$. En vertu de (1), à tout $x \notin C$ on peut faire correspondre un et un seul $c \in C$ tel que $(x, c) \notin U$, et nous appellerons ce sommet $c$ l'associé du sommet $x$.

Si $x, y \in X-C$ et appartiennent à des classes différentes $X_i$ et $X_j$, ils ne peuvent avoir pour associé le même point $c \in C$, car alors $(x, y) \in (C - \{c\})$ serait une clique de $(p+1)$ éléments.

Si $x, y \in X-C$ et appartiennent à la même classe $X_i$, ils ne peuvent avoir des associés $c$ et $d \in C$ avec $c \neq d$, car si cela était, le nombre de classes serait supérieur à $|C| = p$.

Donc le graphe $G$ n'est autre que le graphe $\bar{G}$ décrit plus haut. En augmentant chaque classe $X_i$ de l'élément qui lui est associé dans la clique $C$. on voit que :

$$G = G(n_1, p)$$

On vérifie d'une façon analogue que le théorème est vrai pour les valeurs de $n$ dans la première colonne, et, ainsi, l'énoncé est complètement démontré.

**Critère de TURAN** - Soit $G$ un graphe avec $n$ sommets et $m$ arêtes, et soit $p$ un entier $\ge 2$ ; si $r$ est l'entier $> 0$ et $\le p$ tel que $n-r$ soit divisible par $p$, et si :

$$m > \frac{r(r-1)}{2} + \frac{p-1}{2p} (n^2 - r^2),$$

Alors on a : $\omega(G) > p$

Calculons le nombre $m(n, p)$ d'arêtes du graphe $G(n, p)$ ; si l'on met à part un ensemble $A$ de $r$ éléments pris chacun dans les $r$ premières classes, le nombre d'arêtes entre ces $r$ éléments est $\frac{r(r-1)}{2}$.
Le nombre d'arêtes dans X-A est :

$$ \frac{1}{2} (n - r - q) (n - r) = \frac{n - r}{2p} (pn - pr - n + r) $$

Le nombre d'arêtes entre A et X-A est :

$$ r(p-1)q = \frac{n-r}{p} (pr-r) $$

$$ D'où: m(n,p) = \frac{r(r-1)}{2} + \frac{n-r}{2p} [pn-pr-n+r+2pr-2r] = \frac{r(r-1)}{2} + \frac{p-1}{2p} (n^2-r^2) $$

Le critère énoncé s'en déduit immédiatement.

### Remarque.

On peut facilement vérifier que le critère de Turan implique le résultat de Zarankiewicz tel qu'il était énoncé par celui-ci (mais non pas l'énoncé plus fort que nous avons énoncé plus haut, et qui assure : "toute clique de moins de p éléments est contenue dans une clique de p éléments").

En fait, le théorème de Turan, s'il est bien antérieur à celui de Zarankiewicz, était passé presque inaperçu car il avait été publié dans la langue hongroise ; très récemment, des généralisations du théorème de Turan ont été envisagées par différents auteurs, notamment Kovari, Sos, Turan, Erdős et Moser (1).

(1) T. Kovari, V. T. Sos et P. Turan (Colloquium Math. 3, 1954, p. 50) ont considéré les matrices carrées d'ordre n dont les coefficients sont 0 ou 1, et ont cherché le plus petit nombre $k_p(n)$ de 1 nécessaires pour que l'existence d'un mineur d'ordre p composé exclusivement de 1 soit assurée ; ils ont trouvé en particulier :

$$ k_p(n) < 1 + pn + \left[ (p-1)^p n^{\frac{2p-1}{p}} \right] $$

Ils ont aussi montré que :

$$ \frac{k_2(n)}{n^{3/2}} \rightarrow 1 \text{ quand } n \rightarrow \infty. $$

P. Erdős (Communication orale) a cherché le plus petit entier $f(n, k, 1)$ tel que tout graphe de $n$ sommets et de $f(n, k, 1)$ arêtes contient nécessairement un sous-graphe de $k$ sommets avec 1 arête ; il a déterminé $f(n, 5, 8)$ et $f(n, 6, 11)$, mais pour $f(n, 4, 4)$, on ne connaît même pas de formules asymptotiques. Enfin, P. Erdős et L. Moser ont cherché le plus grand entier $g(n)$ tel que tout graphe orienté complet de $n$ sommets contient un sous-graphe de $g(n)$ sommets pour lequel l'orientation est transitive ; ils ont obtenu :

$$ 2 \log_2 n + 1 \geq g(n) \geq \log_2 n + 1 $$
IV - GRAPHERS GALLAÏENS.

Un graphe G est dit *Gallaïen* si tout cycle élémentaire de G contient une "corde", c'est-à-dire une arête reliant deux sommets non consécutifs de cycle. Notre attention sur cette notion a été attirée récemment par HAJNAL et SURÁNYI, qui ont démontré un théorème que l'on verra à la fin de ce paragraphe. Donnons d'abord quelques exemples.

**Exemple I** - Soit D une droite, J une famille finie d'intervalles sur cette droite, et traçons le graphe G dont les sommets sont les intervalles de J, deux sommets étant reliés s'ils représentent des intervalles non disjoints. Les propriétés caractéristiques d'un tel graphe G ont été étudiées par HAJOS (¹), mais on voit immédiatement que G est gallaïen.

Par contre, cette propriété n'est pas suffisante pour caractériser nos graphes G ; par exemple, le graphe de la figure 4 est gallaïen, mais ne peut représenter 6 intervalles : en effet, les trois intervalles $x_1, x_3$ et $x_5$ sont disjoints deux à deux, et par suite de la symétrie de la figure, on peut les supposer dans cet ordre sur la droite D ; mais alors l'intervalle $x_6$, qui rencontre $x_1$ et $x_5$, doit recouvrir $x_3$, ce qui est contredit par la figure.

<figure><img src="image_13.png" /><figcaption>Figure 6.</figcaption></figure>

**Exemple II** - Soit X un ensemble fini de points sur une droite D, J une famille d'intervalles sur cette droite ; traçons le graphe G dont les sommets sont les points de X, deux sommets étant reliés s'ils représentent deux points recouverts par un même intervalle de J. Là en-core, il est immédiat que le graphe G est gallaïen.

<footnote>(1) G. Hajós : Über eine art von Graphen, Internationale Math. Nachrichten 11, 1957.</footnote>
**Exemple III - Arbres d'Husimi (Physique).**

On appelle _arbre d'Husimi_, un graphe G connexe, dont tous les cycles sont de longueur 3 : c'est donc un graphe gallaïen. Un arbre-d'Husimi est représenté sur la figure 7.

<figure><img src="image_14.png" /><figcaption>Fig. 7.</figcaption></figure>

G : arbre d'Husimi

**Exemple IV** - Si G est un graphe quelconque, son _graphe adjoint_ G* est par définition un graphe dont les sommets sont les arêtes de G, deux sommets étant reliés s'ils représentent des arêtes adjacentes de G.

<figure><img src="image_15.png" /><figcaption>Fig. 8</figcaption></figure>

G* : graphe adjoint du graphe G de la figure 7.
**Le graphe adjoint d'un arbre d'Husimi est gallaïen :** en effet, s'il contenait un cycle élémentaire $\mu^* = [u_1^*, u_2^*...]$ de longueur > 3 et sans cordes, il lui correspond dans $G$ un cycle $\mu$ d'arêtes $u_1, u_2, ...$ (car $\mu^*$ est sans cordes). Ce cycle $\mu$ est de longueur > 3, ce qui est absurde car $G$ est un arbre d'Husimi.

On a pour les graphes gallaïens les propriétés suivantes :

**Propriété 1** - *Tout sous-graphe d'un graphe gallaïen est lui-même gallaïen. (immédiat).*

**Propriété 2** - *Si $[a, b]$ est une arête d'un cycle $\mu$, il existe un cycle $[a, b, c, a]$ avec $c \in \mu$.*

En effet, si $\mu$ est de longueur 3, la propriété est démontrée ; si $\mu$ est de longueur > 3, il admet une corde qui le divise en deux cycles $\mu'$ et $\mu''$. L'un des deux, soit par exemple $\mu'$, contient l'arête $[a, b]$, et s'il est de longueur > 3, on le redivise, etc.

**Propriété 3** - *Soit $x_o \in G$, graphe gallaïen, et soient $a, b \in \Gamma x_o$. S'il existe une chaine joignant $a$ et $b$ sans passer par un autre sommet de $\Gamma x_o$ ni par $x_o$, alors $a$ et $b$ sont adjacents.*

En effet, soit $\mu [a, b]$ le plus court chemin joignant $a$ et $b$ sans passer par $\Gamma x_o \cup \{x_o\}$ ; sa longueur est nécessairement 1, car sinon le cycle $\mu [a, b] + [b, x_o, a]$ n'aurait ni corde d'extrémité $x_o$ (car $\mu$ ne passe pas par $\Gamma x_o$) ni autres cordes (car $\mu$ est de longueur minimum).

**Propriété 4** - *Si $G$ est un graphe Gallaïen k-critique, le sous-graphe engendré par $\Gamma x_o$ est connexe.*

En effet, supposons qu'il n'en soit pas ainsi : soient $y_1$ et $y_2$ deux sommets de $\Gamma x_o$ appartenant à deux composantes distinctes. On peut joindre $y_1$ et $y_2$ par chaine élémentaire $\mu$ ne passant pas $x_o$ (car $x_o$ n'est pas un point d'articulation de $G$, d'après la propriété 5, § 1). Soit donc $\mu'$ une chaine partielle de $\mu$ joignant deux composantes distinctes de $\Gamma x_o$ sans toucher $\Gamma x_o$ (en dehors de ses extrémités). D'après la propriété 3, ces deux composantes sont jointes par une arête: absurde.
**Théorème 1** - Si $G$ est un graphe gallaien on a :

$$ \gamma(G) = \omega(G) $$

Nous ne donnerons pas ici la démonstration générale, qui fait appel à la théorie de la désarticulation des graphes ; bornons-nous à démontrer la propriété pour un graphe gallaien $G$ avec $\omega(G) < 4$.

En effet, si $\omega(G) = 1$, le graphe est constitué par des points isolés, donc $\gamma(G) = 1$.

Si $\omega(G) = 2$, le graphe n'admet pas de cycles (en vertu de la propriété 2 et de $\omega(G) < 3$), donc, d'après le théorème de König, $\gamma(G) = 2$.

Si $\omega(G) = 3$, supposons que $\gamma(G) > 3$ et déduisons-en une absurdité (on aura alors bien démontré que $\gamma(G) = 3$, car $\gamma(G) > \omega(G) = 3$).

Comme $\gamma(G) > 3$, on peut toujours supposer que $G$ est 4-critique (quitte à le remplacer par un sous-graphe 4-critique $G_0$, pour lequel on a évidemment $\omega(G_0) \le 3$).

Ainsi, si $x_0 \in G$, son degré $d(x_0)$ est $\ge 3$ (en vertu de la propriété 2, § 1) ; de plus, $\Gamma x_0$ est connexe (propriété 4) et ne contient pas de cycles (car sans cela $\Gamma x_0$ contiendrait un triangle, et $\omega(G) = 4$) : c'est donc une chaine élémentaire d'au moins trois sommets : [a, b, c, ...].

Γa consiste également en une chaine élémentaire, et comme $\Gamma a \cap \Gamma x_0 = \{b\}$ (puisque $\Gamma x_0$ n'a pas de cycles), cette chaine est de la forme $[x_0, b, x_1, ...]$, avec $x_1 \notin \Gamma x_0$.

Soit $C_1$ la composante de sommets qu'on peut atteindre de $a$ sans rencontrer à nouveau $\Gamma x_0 \cup \{x_0\}$; on a $C_1 \ne \emptyset$ (car $x_1 \in C_1$). Les seuls points de $\Gamma x_0$ adjacents à $C_1$ sont $a$ et $b$ (en vertu de la propriété 3) ; donc $\{x_0, a, b\}$ est un ensemble d'articulation pour le graphe, (puisque sa suppression disconnexe $x_1$ et $c$) ; mais un graphe 4-critique n'ayant pas d'ensemble d'articulation qui suit un triangle (propriété 4, § 1), on a la contradiction cherchée.

<figure><img src="image_16.png" /><figcaption>Fig. 9.</figcaption></figure>
Avant d'aller plus loin dans l'étude des graphes gallaiens, introduisons quelques notations.

On sait que l'on désigne par $\alpha(G)$ le plus grand nombre d'éléments d'un ensemble stable ("nombre de stabilité interne"). Considérons une partition $C$ des sommets du graphe en cliques $C_1, C_2, \dots$, et désignons par $\wp(G)$ le plus petit nombre de cliques d'une telle partition.

Pour tout ensemble stable $S$ et pour toute partition $C$, on a :

$$|S| < |C|$$

En effet, une clique $C \in C$ ne peut contenir qu'un seul élément de $S$. On a donc :

$$\alpha(G) = \max |S| \le \min |C| = \wp(G)$$

**Théorème 2** - (HAJNAL-SURANYI) - Si $G$ est un graphe gallaien, on a :

$$\alpha(G) = \wp(G)$$

Le théorème est vrai si $\alpha(G) = 1$, car alors $G$ est une clique, et $\wp(G) = 1$.

Supposons le théorème vrai pour $\alpha(G) < k$, et démontrons que c'est encore vrai pour un graphe $G$ donné avec $\alpha(G) = k$.

Soit $S = \{s_0, s_1, s_2, \dots, s_{k-1}\}$ un ensemble stable maximum de $G$, et soit $G'$ le sous-graphe déduit de $G$ en supprimant $\{s_0\} \cup \Gamma s_0$ : il a des composantes connexes $C_1, C_2, \dots$.

1/ - L'ensemble $S \cap C_i$ est stable ; il n'existe pas dans $C_i$ un ensemble stable $S_i$ avec $|S_i| > |S \cap C_i|$, car si cela était, on pourrait former avec $\{s_0\}, S_1$, et les $S \cap C_j$, (avec $j \ne i$) un ensemble stable du graphe $G$ ayant plus de $k$-éléments. En définitive, on a :

$$|S \cap C_i| = \alpha(C_i) = \wp(C_i)$$

2/ - Soit $G_0$ l'ensemble des sommets $x \in \Gamma s_0$ avec :

$$\alpha(C_i \cup x) = \alpha(C_i) + 1 \quad (\text{pour tout } i)$$

Si $x, y \in G_0$, et si ces deux sommets sont adjacents à une même composante $C_i$, ils sont reliés entre eux (propriété 3). S'ils ne sont pas adjacents à une même composante $C_i$, ils sont également reliés entre eux, car sans cela on pourrait former dans $G$ un ensemble stable avec plus de $k+1$ éléments en prenant $x, y$, et des ensembles stables $S_i \subset C_i$ avec :

$$\alpha(C_i) = |S_i|$$
$$ \Gamma x \cap S_i = \emptyset \quad (\text{si x adjacent à } C_i) $$

$$ \Gamma y \cap S_i = \emptyset \quad (\text{si y adjacent à } C_i) $$

En définitive, le graphe $G_0$ est une clique.

3/ - Si $x \notin G_0$, $x \in \Gamma s_0$, il existe une composante $C_i$ pour laquelle

$$ \alpha(C_i \cup x) = \alpha(C_i) $$

on peut alors ajouter $x$ à la composante $C_i$ ; de proche en proche, la composante $C_i$ deviendra un ensemble $C'_i \supset C_i$ ; deux sommets de $C'_i - C_i$ , étant adjacents à $C_i$ , sont reliés entre eux (propriété 3) ; donc $C'_i - C_i$ est une clique. Un ensemble stable maximum $S'_i$ de $C'_i$ a au plus un élément y appartenant à cette clique, donc :

$$ \alpha(C_i) \le \alpha(C'_i) = |S'_i| = \alpha(y \cup C_i) = \alpha(C_i) $$

En définitive, on a :

$$ \alpha(C'_i) = \alpha(C_i) $$

4/ - Le théorème étant vrai pour $\alpha(G) < k$, on peut partitionner $C_i$ en $\alpha(C_i)$ cliques disjointes.

Avec l'ensemble $G_0 \cup s_0$, qui forme une clique supplémentaire, on pourra partitionner $G$ en :

$$ 1 + \alpha(C_1) + \alpha(C_2) + \dots = k \text{ cliques disjointes. } \qquad \text{C.Q.F.D.} $$

**Corollaire** - Si $G'$ est le complémentaire d'un graphe $G$ gallaien, on a :

$$ \gamma(G') = \omega(G') $$

$G'$ est par définition un graphe qui a les mêmes sommets que $G$, deux sommets étant reliés dans $G'$ si et seulement si ils ne sont pas reliés dans $G$ ; on a donc :

$$ \gamma(G') = \omega(G) $$

$$ \omega(G') = \alpha(G) $$

D'après le théorème 2, on a bien $\gamma(G') = \omega(G')$.
**Application 1** - Si J est une famille finie d'intervalle sur une droite, et si k est le nombre maximum d'intervalle dis joints deux à deux qu'on peut distinguer, alors il existe sur la droite k points tels que tout intervalle contienne au moins l'un d'entre eux.

En effet, le graphe G représentant les intersections des inter-
valles est Gallaïen ; toute clique de G représente une famille d'inter-
valles ayant un point commun, en vertu du théorème de HELLY (1).
On a donc bien l'énoncé.

Application 2 - Si J est une famille d'intervalle sur une droite, et si k est le nombre maximum d'intervalle ayant une intersection non vide, alors on peut colorier les intervalles avec k couleurs de sorte que deux intervalles de même couleur ne se rencontrent pas.

Il s'agit de montrer que si $\omega(G) = k$, on a $\gamma(G) = k$ ; ceci est vrai.

V - GRAPHES PSEUDO-GALLAIENS.

On peut donner une légère modification à la notion de graphe
Gallaïen qui entraîne des propriétés remarquables ; on dira qu'un graphe
G est pseudo-Gallaïen si "on a les axiomes :

(I) - Tout cycle de longueur impaire > 3 admet une corde ;

(II) - Pour tout sommet x, l'ensemble Bx = {x} u Γx est la réu-
nion de deux cliques C_x et C'_x telles que les ensembles disjoints C_x - C'_x
et C_x - C'_x ne soient reliés par aucune arête.

Récemment, T. GALLAI (2) a étendu le théorème de HAJNAL.

<footnote>(1) cf. par exemple : C. BERGE, *Espaces Topologiques et Fonctions Multivoques* (Dunod édit.), 1959, p. 211.</footnote>

<footnote>(2) T. GALLAI, à paraître dans les Annales Universitatis Scientiarum Budapes-
tinensis de Rolando Eötvös nominatae, Sectio Math.</footnote>
SURANYI aux graphes pour lesquels tout cycle de longueur impaire est triangulé - ce qui représente un axiome légèrement plus fort que notre axiome (I) -.

Rappelons tout d'abord quelques définitions :

Un **multigraphe** (X,U) est formé par un ensemble de sommets X, un ensemble d'arêtes U, mais il peut y avoir dans U plusieurs arêtes distinctes $[x,y]_1, [x,y]_2, \dots$ reliant le même couple de sommets x, y. Le **degré** d'un sommet x est alors le nombre $d(x)$ d'arêtes ayant au moins une extrémité en x ; on a $d(x) \ge |\Gamma x|$. Un multigraphe est dit simple si ses sommets sont divisés en deux classes X et Y, deux sommets de la même classe n'étant pas reliés par une arête de U.

Généralisant un résultat connu pour le graphe simple, démontrons :

**Théorème 1** - Soit $H = (X, Y, U)$ un multigraphe simple, $m = \max_{x \in X} d(x)$ son degré maximum : il est possible de colorier les arêtes de $H$ avec $m$ couleurs de sorte que deux arêtes ayant une extrémité commune soient de différentes couleurs.

1/ - Montrons d'abord que si :

$$d(x) = m \quad (x \in H),$$

on peut **coupler** X dans Y (cf. [1], p. 92).

En effet, si $A \subset X, B \subset Y, |B| < |A|$, de l'ensemble $A$ il sort $m|A|$ arêtes, dans l'ensemble $B$ il arrive $m|B|$ arêtes ; comme $m|B| < m|A|$, on ne peut avoir $\Gamma A \subset B$. Donc $|\Gamma A| \ge |A|$, et ceci pour tout $A \subset X$: d'après le théorème de KONIG-HALL, ([1], p. 92), on peut bien coupler X dans Y.

2/ - Montrons qu'il existe un couplage utilisant à la fois tous les sommets x avec $d(x) = m$, et tous les sommets y avec $d(y) = m$.

En effet, en faisant m copies du multigraphe H, on peut construire un multigraphe $H_0$ pour lequel H est un sous-graphe partiel, et pour lequel :

$$d_0(x) = m \quad (x \in H_0)$$

A un couplage complet de $H_0$ correspond dans H un couplage ayant la propriété désirée.

3/ - On peut colorier les arêtes de H de la façon suivante : avec
une première couleur, on colorie les arêtes d'un couplage utilisant tous les sommets de degré m ; il restera un multigraphe $H_1$ de degré maximum m - 1, et dans $H_1$, on coloriera avec une deuxième couleur les arêtes d'un couplage utilisant tous les sommets de degré m - 1 ; etc.

De cette façon, avec m couleurs exactement, on aura bien colorié toutes les arêtes de H.

**Théorème 2** - La condition nécessaire et suffisante pour que G soit un graphe pseudo-gallaien est qu'il soit l'associé d'un multigraphe simple $\mathbb{H}$.

1/ - Montrons que si H est un multigraphe simple, $G = H^*$ est pseudo-gallaien.

Par définition, le graphe associé $H^*$ a ses sommets représentant des arêtes de H, deux sommets étant reliés s'ils représentent des arêtes adjacentes de H. A tout cycle élémentaire $\mu^* = [u_1^*, u_2^*, \dots, u_k^*]$ de $H^*$, avec $k > 3$, et sans cordes, il correspond dans H un cycle $\mu = (u_1, u_2, \dots, u_l)$ de même longueur ; comme H est un multigraphe simple, $\mu$ est pair, donc $\mu^*$ est pair : $H^*$ satisfait donc à l'axiome (I). Les axiomes (II) sont immédiats.

2/ - Montrons que si G est pseudo-gallaien, on peut construire un multigraphe simple H avec $G = H^*$.

Considérons un graphe $G = (X, \Gamma)$ pseudo-Gallaien, et faisons la convention suivante : si $Bx = \{x\} \cup \Gamma x$ est une clique, on prendra pour $C_x$ et $C'_x$ les ensembles $\{x\}$ et $Bx$.

3/ Remarquons que toute clique C contenue dans $Bx$ est contenue soit dans $C_x$ soit dans $C'_x$ ; en effet, sinon, l'on aurait $y, y' \in C_x$, $y \in C_x - C'_x$, $y' \in C'_x - C_x$ ; donc $(y, y')$ n'est pas une arête, ce qui contredit $y, y' \in C$.

4/ Montrons que si $y \in C_x$, l'ensemble $C_x$ est égal à $C_y$ (ou à $C'_y$).

Si $C_x \subset C'_x$, c'est évident, car $Bx$ est une clique, donc

$$C_x = \{x\} = \{y\} = C_y$$

Si $C_x \not\subset C'_x$, il existe un sommet $t \in C_x - C'_x$.

Comme $C_x$ est une clique contenue dans $Bx$, on peut écrire en vertu de 1°, que $C_x \subset C_y$ ; si l'on avait $C_x \neq C_y$, il existerait un sommet $t'$ avec $t' \in C_y$, $t' \notin C_x$. Donc $t' \in C'_x - C_x$, donc $(t, t')$ n'est pas une arête, ce qui contredit $t, t' \in C_y$. On a donc $C_x = C_y$.
5/ De cette façon, les différents ensembles $C_x$ et $C'_x$ constituent une famille (K) de cliques telle que tout sommet $x$ appartienne à exactement deux cliques de (K). Construisons le graphe $H$ de la façon suivante : ses sommets représentent les cliques de la famille (K), et si deux cliques $C, C' \in (K)$ ont en commun des points $x_1, x_2, \dots, x_k$, on joindra les sommets $C$ et $C'$ correspondants par $k$ arêtes que l'on dénotera $u_1, u_2, \dots, u_k$.

Si deux arêtes $u_i$ et $u_j$ de $H$ concourent en un sommet $C$, les points $x_i$ et $x_j$ de $H$ appartiennent à une même clique $C \in (K)$, donc sont reliés.

Inversement, si deux points $x_i$ et $x_j$ de $G$ sont reliés, ils constituent une clique, donc, en vertu de 1°, ces deux points appartiennent à un même $C \in (K)$, donc les arêtes $u_i$ et $u_j$ de $H$ concourent au même sommet $C$.

On a donc bien $G = H^*$.

6/ Montrons que $H$ est un multigraphe simple. $H$ n'a pas de cycles de longueur 3, car alors il existerait trois cliques $C_1, C_2, C_3 \in (K)$ se rencontrant deux à deux, donc $C_1 - C_2$ et $C_2 - C_1$ seraient reliés par une arête, ce qui contredit l'axiome II. D'autre part, le graphe $H$ n'a pas de cycles élémentaires de longueur impaire > 3, car si $u_1, u_2, \dots, u_{2k+1}$ sont les arêtes d'un tel cycle, les sommets $x_1, x_2, \dots, x_{2k+1}$ qui leur correspondent dans $G$ déterminent un cycle de longueur impaire > 3, sans cordes, ce qui contredit l'axiome I.

Le multigraphe $H$, qui n'a pas de cycles de longueur impaire, est donc simple.

**Théorème 3** - Dans un graphe $G$ pseudo-gallaien, on a :

$$ \omega(G) = \gamma(G) $$

En effet, soit $H$ le multigraphe simple tel que $G = H^*$, et soit $m$ le degré maximum de $H$. On a, en vertu du théorème 1 :

$$ \gamma(G) = m \le \omega(G) $$

D'autre part, on a :

$$ \gamma(G) \ge \omega(G) $$

D'où :

$$ \gamma(G) = \omega(G) $$
**Théorème 4** - Dans un graphe G pseudo-gallaien, on a :

$$ \alpha(G) = \wp(G) $$

En effet, soit H le multigraphe simple tel que $G = H^*$, et k le nombre maximum d'arêtes d'un couplage de H. D'après un résultat bien connu de KÖNIG ([1], p. 98), k est égal au nombre minimum de sommets qu'on peut distinguer de sorte que toute arête de H ait une de ses extrémités en un sommet distingué. Ces sommets distingués forment dans G une partition en clique C, les arêtes du couplage forment un ensemble stable S, et l'on a $|S| = |C|$. D'où :

$$ \alpha(G) = \wp(G) $$

**Remarque**

Si le graphe G, au lieu d'être pseudo-Gallaïen, satisfait seulement à l'axiome I, le théorème 3 n'est plus vrai, comme le montre l'exemple suivant construit par M. G houila-Houri [10] :

G est un graphe de 7 sommets, dénotés a, b, c, d, e, f, g, avec pour arêtes : ac, ad, ae, af, bd, be, bf, bg, ce, cf, cg, df, dg, eg; le degré de chaque sommet est donc 4. Montrons que le graphe G satisfait à l'axiome I: il n'existe pas de cycles élémentaires, sans cordes, de longueur 7, car un tel cycle utiliserait tous les sommets, et le degré de chaque sommet devrait être égal à 2 ; il n'existe pas davantage de cycles élémentaires, sans cordes, de longueur 5, car un tel cycle laisserait de côté deux sommets x et y, tout autre sommet (étant de degré 4) serait relié à x et à y, et l'on aurait $d(x) \ge 5$, $d(y) \ge 5$.

On voit de même qu'il ne peut exister une clique de 4 éléments, car le complémentaire d'une telle clique serait un ensemble D de 3 éléments, chaque sommet de la clique serait relié à D par une arête, et il sortirait de D exactement 4 arêtes : absurde, car l'un au moins des trois sommets de D serait de degré inférieur à 4. On a donc $\omega(G) = 3$.

Par ailleurs, si l'on essaye de colorier de proche en proche les sommets de G avec 3 couleurs, on s'aperçoit que $\gamma(G) = 4$ ; on a donc bien $\gamma(G) \neq \omega(G)$.

# VI - APPLICATIONS AU PROBLEME DES QUATRE COULEURS.

Si l'on veut colorier les faces du graphe planaire G avec quatre couleurs, on peut toujours supposer que G est :
1/ - sans isthmes (un isthme est une arête dont la suppression disconnecte le graphe);

2/ - homogène de degré 3 (tous les sommets sont de degré 3) car si $d(x) > 3$, on posera une face suffisamment petite sur $x$.

**Théorème 1** - Si $G$ est un graphe homogène de degré 3 sans isthmes, on peut colorier les arêtes de $G$ avec 4 couleurs (sans que deux arêtes adjacentes ne soient de même couleur).

En effet considérons le graphe adjoint $G^*$, qui est homogène de degré 4; $G^*$ ne contient pas une clique $\{u,v,w,x\}$ de 4 éléments, car une telle clique ne peut donner une configuration correcte d'arêtes dans $G$.

Donc d'après le théorème de BROOKS, $\gamma(G^*) \le 4$. C.Q.F.D.
(Ce résultat précise le théorème 5 de [1], p. 189).

**Théorème 2** - (HEAWOOD) - Si $G$ est un graphe planaire homogène de degré 3 et sans isthmes, les trois conditions suivantes sont équivalentes:

(1) - On peut colorier les faces de $G$ avec 4 couleurs ;

(2) - On peut colorier les arêtes de $G$ avec 3 couleurs ;

(3) - On peut affecter chaque sommet $x$ d'un coefficient $p(x)$, égal à $+1$, ou à $-1$, de sorte que le contour de chaque face $\mu$ vérifie :

$$ \sum_{x \in \mu} p(x) \equiv 0 \pmod{3} $$

(1) $\Rightarrow (2)$ : Si l'on peut colorier les faces de $G$ avec 4 couleurs : $\alpha, \beta, \gamma, \delta$, on attribue le symbole 1 aux arêtes séparant une face $\alpha$ et une face $\beta$, ou une face $\gamma$ et une face $\delta$ ; le symbole 2 à celles séparant une face $\alpha$ et une face $\gamma$, ou une face $\beta$ et une face $\delta$ ; le symbole 3 à celle séparant une face $\alpha$ et une face $\delta$, ou une face $\beta$ et une face $\gamma$.

Deux arêtes adjacentes ne peuvent être marquées du même symbole (car sinon il y aurait deux faces adjacentes de la même couleur) : on a donc bien (2).

(2) $\Rightarrow (1)$ : Supposons qu'on puisse colorier les arêtes de $G$ avec trois couleurs : 1, 2 et 3. Les arêtes des types 1 et 2 forment un graphe homogène de degré 2, et l'on peut donc colorier ses régions avec seulement deux couleurs $p$ et $q$ ; les arêtes des types 1 et 3 forment aussi un graphe dont on peut colorier les régions avec deux couleurs $r$ et $s$. Supposons dans le graphe $G$ les couleurs trouvées : chaque pays portera une des quatre combinaisons $pr, ps, qr, qs$. Deux faces séparées
par une arête du type 1 porteront des combinaisons distinctes, et il en est de même pour deux faces séparées par une arête du type 2 ou 3; on a ainsi obtenu la coloration cherchée. (1).

(2) ⇒(3) : Colorions les arêtes de G avec trois couleurs : 1, 2 et 3. Posons $p(x) = +1$ si les trois arêtes incidentes au sommet $x$ sont dans l'ordre : 1, 2, 3 avec le sens trigonométrique, et posons $p(x) = -1$ dans le cas contraire. Parcourons le contour d'une face $\mu$ dans le sens trigonométrique en partant d'une arête quelconque : chaque fois qu'on traverse un coefficient $+1$, l'indice de l'arête qu'on suit subit une permutation tournante négative ; chaque fois qu'on traverse un coefficient $-1$, la permutation est positive. Lorsqu'on sera revenu sur l'arête initiale, la somme algébrique des coefficients rencontrés aura donc été un multiple de 3.

(3) ⇒(2) : Soient des coefficients $p(x)$ conformes à (3) ; nous allons d'abord montrer que la somme algébrique des $p(x)$ le long d'un cycle $\nu$ quelconque est encore un multiple de 3 ; on peut évidemment se borner au cas où $\nu$ est un cycle élémentaire, et, par conséquent, contient des faces $\mu_1, \mu_2, \dots$. On a :

$$ \sum_{x \in \mu} p(x) = \sum_{x \in \mu_1} p(x) + \sum_{x \in \mu_2} p(x) + \dots - 3 \sum_{x \text{ est intérieur au cycle } \nu} p(x) $$

On trouve donc bien au second membre un multiple de 3.

Partons d'une arête quelconque, que l'on affecte de l'indice 1 ; à l'aide des coefficients $p(x)$, on peut affecter de proche en proche chaque arête d'un indice 1, 2 ou 3 de sorte que les trois arêtes incidentes à un sommet $x$ sont dans l'ordre 1, 2, 3 avec le sens trigonométrique si $p(x) = +1$, et avec le sens inverse si $p(x) = -1$. Il n'y aura jamais de contradictions, car si l'on pouvait affecter une même arête de deux indices différents, la somme algébrique des $p(x)$ le long d'un cycle $\nu$ ne serait pas un multiple de 3.

On peut donc bien colorier les arêtes de G avec les couleurs : 1, 2, 3.

**Corollaire 1** - Si chaque face est constituée par un nombre d'arêtes multiple de 3, on peut colorier les faces de G avec 4 couleurs.

En effet, si l'on prend $p(x) = +1$ pour tout sommet $x$, la condition (3) du théorème de HEAWOOD est satisfaite.

**Corollaire 2** - Si chaque face est constituée par un nombre d'arêtes multiple de 2, on peut colorier les faces de G avec 4 couleurs.

(1) Cette démonstration est plus simple que celle de [1], puisqu'on ne fait pas usage du lemme de la p. 214.
En effet, si $v$ est un cycle élémentaire, il contient des faces $\mu_1, \mu_2, \dots$ etc. ; sa longueur $l(v)$ vérifie :

$$1(v) = 1(\mu_1) + 1(\mu_2) + \dots + 2 \text{ (nombre d'arêtes intérieures à v)}$$

On voit sur cette formule que $v$ est de longueur paire, et il en est de même d'un cycle quelconque (qui est somme de cycles élémentaires). Donc, d'après le théorème de KÖNIG ([1], p. 31), on peut affecter chaque sommet $x$ d'un coefficient $p(x) = +1$ ou $-1$ de sorte que deux sommets adjacents n'aient jamais le même coefficient. Avec les $p(x)$ ainsi définis, la condition (3) du théorème de HEAWOOD est satisfaite.

Considérons maintenant le problème sous sa forme duale, et cherchons à colorier les sommets d'un graphe planaire $G$. Comme on a $\omega(G) \le 4$ (cf. [1], p. 209), il suffirait donc de démontrer que $\gamma(G) = \omega(G)$.

Citons, en esquissant seulement la démonstration, quelques résultats qui découlent des paragraphes précédents.

**Théorème 3** - *Un graphe planaire non coloriable avec quatre couleurs contient soit deux sommets de degré 5, soit un sommet de degré > 5.*

(Immédiat, d'après le théorème de DIRAC).

**Théorème 4.** (GRÖTZSCH) - *Un graphe planaire $G$ sans triangle est coloriable avec 3 couleurs.*

En effet, on peut plonger $G$ dans un graphe $G_0$ gallaßen sans former de cliques de quatre éléments ; on a alors, d'après le théorème 1, § 4 :

$$\gamma(G) \le \gamma(G_0) = \omega(G_0) = 3$$

**Théorème 5.** (DIRAC) - *Soit $G$ un graphe traçable sur une surface fermée du genre $g > 0$ sans intersections d'arêtes, et posons :*

$$n_g = \text{partie entière} \left( \frac{7}{2} + \frac{1}{2} \sqrt{48g+1} \right)$$

$$\underline{\text{Si } \gamma(G) = n_g, \text{ on a } \omega(G) = n_g.}$$

On sait déjà que $\omega(G) \le \gamma(G) \le n_g$ (Heawood) ; si $G$ est k-critique avec $\omega(G) < k$, on a, d'après le corollaire de DIRAC et la formule d'Euler :

$$(k-1)n+h-3 \le 2m \le 6n+12 \quad (g-1)$$
Si $g > 5$, on en déduit aisément $k < n_g$, ce qui contredit l'hypothèse - Si $g = 1, 2, 3, 4$, la vérification se fait de même - On a donc bien le résultat cherché.

Bien entendu, ce dernier résultat ne s'applique pas aux graphes planaires (cas $g = 0$).

BIBLIOGRAPHIE

[1] C. BERGE - Théorie des graphes et ses applications, Paris 1958
(Dunod édit).

[2] R. L. BROOKS - On colouring the nodes of a network, *Proc. Camb. Phil. Soc.* **37**, (1941), p. 194.

[3] G. A. DIRAC - Some Theorems on abstract graphs, *Proc. London Math. Soc.* **2**, (1952), p. 77.

[4] G. A. DIRAC - The structure of k-chromatics graphs, *Fund. Math.* **40**, 1953, p. 50.

[5] G. A. DIRAC - A Theorem of R. L. Brooks and a conjecture of H. Hadwiger, *Proc. London Math. Soc.*, **7**, 1957, p. 161.

[6] H. GROTZSCH - Zur Theorie der diskreten Gebilde, **7**, Mitteilung, Wiss. Zeitschr. Univ. Halle, Math. Nat. VIII, **1**, 1958, p. 109.

[7] A. HAJNAL et J. SURÁNYI - Über die auflösung von graphen in vollständige teilgraphen, *Ann. Univ. Sc. Budapestinensis* **1**, 1958, p. 113.

[8] J. MYCIELSKI - Sur le coloriage des graphes, *Coll. Math.* **3**, 1955, p. 161.

[9] L. VIGNERON - Sur la parité du nombre de composantes de Tant des réseaux cubiques, C.R. Ac. Sc., **249**, 1959, p. 2462.

[10] A. GHOUILA-HOURI - Sur une conjecture de C. Berge, (non public).

[11] P. TURAN - On the theory of graphs, Colloquium Math. 3, 1954, p. 19.

[12] K. ZARANKIEWICZ - Sur les relations symétriques dans l'ensemble fini, Colloquium Math. 1, 1947, p. 10.