Graphes : degrés, chemins, arbres¶

Domaine : Combinatoire · Niveau : intermédiaire · Prérequis : Double comptage

L'idée¶

Un graphe est un ensemble de sommets reliés par des arêtes. Beaucoup de problèmes deviennent clairs une fois traduits en graphe : des personnes qui se connaissent, des villes reliées par des routes, des îles et des ponts, des nombres dont la somme est un carré. On choisit ce que sont les sommets et ce que sont les arêtes, puis on applique quelques résultats généraux.

Vocabulaire. Le degré d'un sommet est son nombre de voisins. Un chemin est une suite de sommets voisins distincts ; un cycle est un chemin qui revient à son départ. Un graphe est connexe si deux sommets quelconques sont reliés par un chemin ; sinon, il se découpe en composantes connexes. Un arbre est un graphe connexe sans cycle. Dans un graphe orienté, les arêtes ont un sens ; un tournoi est un graphe complet orienté.

Résultats à connaître¶

Thème	Résultat
Degrés	\(\sum \deg = 2 \times\) (nombre d'arêtes) ; le nombre de sommets de degré impair est donc pair
Arbres	Pour un graphe à \(n\) sommets, deux des trois propriétés « connexe », « sans cycle », « \(n - 1\) arêtes » entraînent la troisième ; un arbre à au moins \(2\) sommets a au moins \(2\) feuilles
Cycles	Un graphe à \(n\) sommets et au moins \(n\) arêtes contient un cycle ; si tous les degrés sont \(\geq 2\), aussi
Composantes	Ajouter une arête diminue le nombre de composantes d'au plus \(1\) : un graphe à \(n\) sommets et \(e\) arêtes a au moins \(n - e\) composantes
Graphes bipartis	On peut colorier les sommets en deux couleurs sans arête monochrome si et seulement s'il n'y a pas de cycle impair
Parcours eulériens	Un graphe connexe a un circuit passant une fois par chaque arête si et seulement si tous ses degrés sont pairs
Graphes planaires	Formule d'Euler : \(S - A + F = 2\) (sommets, arêtes, faces, graphe connexe)
Triangles	Théorème de Mantel : sans triangle, au plus \(\frac{n^2}{4}\) arêtes (exemple résolu)
Ramsey	Parmi \(6\) personnes, \(3\) se connaissent mutuellement ou \(3\) ne se connaissent pas du tout

Exemple résolu¶

Problème (théorème de Mantel)

Un graphe à \(n\) sommets ne contient aucun triangle. Montrer qu'il a au plus \(\dfrac{n^2}{4}\) arêtes.

Notons \(e\) le nombre d'arêtes et \(d(v)\) le degré du sommet \(v\).

Étape 1 : une inégalité locale. Si \(u\) et \(v\) sont reliés, ils n'ont aucun voisin commun (sinon on aurait un triangle). Leurs voisinages sont donc disjoints parmi les \(n\) sommets :

\[d(u) + d(v) \leq n.\]

Étape 2 : sommer sur les arêtes. On somme sur les \(e\) arêtes. Dans le membre de gauche, chaque sommet \(v\) apparaît une fois pour chacune de ses \(d(v)\) arêtes (double comptage) :

\[\sum_{v} d(v)^2 \leq n\,e.\]

Étape 3 : minorer la somme des carrés. Par Cauchy-Schwarz et le lemme des poignées de main,

\[\sum_v d(v)^2 \geq \frac{1}{n}\Big(\sum_v d(v)\Big)^2 = \frac{4e^2}{n}.\]

Étape 4 : conclure. On obtient \(\frac{4e^2}{n} \leq n\,e\), soit \(e \leq \frac{n^2}{4}\). La borne est atteinte pour \(n\) pair par le graphe biparti complet : deux groupes de \(\frac{n}{2}\) sommets, chaque sommet relié à tous ceux de l'autre groupe.

L'hypothèse « pas de triangle » est locale (elle porte sur une arête et ses extrémités) ; on l'a transformée en information globale en sommant sur toutes les arêtes. C'est le schéma le plus courant en théorie des graphes.

Comment le reconnaître¶

L'énoncé parle de relations entre paires d'objets : se connaître, être relié, avoir joué ensemble, avoir une somme qui est un carré.
On parle de réseaux : routes, ponts, vols, portes entre des pièces.
Une propriété de parité sur des connexions : penser aux degrés.
On veut colorier des objets en deux couleurs avec des contraintes entre paires : graphe biparti, cycles impairs.
On demande un parcours qui passe partout une seule fois.

Techniques classiques¶

Situation	Technique
Problème sur des paires	Le traduire en graphe : choisir sommets et arêtes
Parité d'un nombre de connexions	Somme des degrés, sommets de degré impair
Borne sur le nombre d'arêtes	Inégalité locale sur chaque arête ou chaque sommet, puis sommer
Montrer qu'il existe un cycle ou un chemin long	Le plus long chemin (principe extrémal)
Compter des composantes	Chaque arête en fusionne au plus deux
Figure plane découpée en régions	Formule d'Euler et double comptage des côtés
Relations orientées (matchs, routes à sens unique)	Tournois, degrés entrants et sortants

Exercices d'échauffement¶

Montrer que, dans une soirée, le nombre de personnes qui ont serré un nombre impair de mains est pair.
Montrer que parmi \(6\) personnes, on en trouve \(3\) qui se connaissent deux à deux, ou \(3\) qui ne se connaissent pas deux à deux.
Montrer que dans un graphe à \(n \geq 2\) sommets, deux sommets ont le même degré.
Montrer qu'un arbre à \(n \geq 2\) sommets a au moins deux sommets de degré \(1\).
Un graphe connexe a exactement deux sommets de degré impair. Montrer qu'on peut le parcourir en passant exactement une fois par chaque arête.

Graphes dans la shortlist¶

2019 C5 : on reformule en graphe ; le nombre de sommets de degré impair est pair, et un arbre n'a pas de cycle.
2020 C4 : un graphe à \(d\) arêtes sans cycle a au moins \(d + 1\) sommets.
2019 C4 : régions et portes ; chaque arête diminue le nombre de composantes d'au plus \(1\).
2023 C4, solution 1 : le graphe obtenu a un circuit eulérien, donc il est connexe.
2018 C7 : la formule d'Euler et les degrés d'un graphe de cercles.

Pour approfondir : Objectif Olympiades de Mathématiques, tome 4 (M. Aassila), p. 195 à 208 (notions de base, chaînes et cycles, graphes orientés, récapitulatif p. 208), p. 213 (degrés), p. 219 (théorème de Turán, qui généralise Mantel), p. 225 (arbres), p. 229 (coloration), p. 236 (graphes eulériens), p. 239 (graphes hamiltoniens), p. 249 (graphes planaires et formule d'Euler), p. 259 (théorie de Ramsey), p. 273 (couplages), p. 276 à 298 (exercices de trois niveaux).

Problèmes de la shortlist¶

40 problèmes · difficulté moyenne : ★★★★★ (3,5) · dont 10 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 4 · 2 ★ : 6 · 3 ★ : 9 · 4 ★ : 8 · 5 ★ : 13

Problème	Difficulté	Concepts
2021 N2 · OIM P1	★☆☆☆☆	Principe des tiroirs
2020 N2	★☆☆☆☆	Résidus quadratiques · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme
2018 C2 · OIM P4	★☆☆☆☆	Coloriages et pavages · Jeux et stratégies gagnantes
2015 C2 · OIM P1	★☆☆☆☆	Géométrie combinatoire : enveloppe convexe, points du réseau · Double comptage · Principe des tiroirs
2021 C4	★★☆☆☆	-
2020 C4	★★☆☆☆	Principe extrémal · Sommes, télescopage et transformation d'Abel
2019 C4	★★☆☆☆	Géométrie combinatoire : enveloppe convexe, points du réseau · Invariants et monovariants · Récurrence et constructions récursives
2013 C3	★★☆☆☆	Coloriages et pavages · Récurrence et constructions récursives
2011 C4	★★☆☆☆	Double comptage · Principe des tiroirs
2009 N1 · OIM P1	★★☆☆☆	Divisibilité, PGCD et algorithme d'Euclide · Théorème des restes chinois
2023 C4	★★★☆☆	Invariants et monovariants · Récurrence et constructions récursives
2019 C5 · OIM P3	★★★☆☆	Invariants et monovariants · Principe extrémal
2017 A5	★★★☆☆	Double comptage
2015 C5 · OIM P6	★★★☆☆	Principe des tiroirs · Double comptage · AM-GM et moyennes
2013 A4	★★★☆☆	Double comptage · Récurrence et constructions récursives
2012 C5	★★★☆☆	Coloriages et pavages · Double comptage
2010 C2	★★★☆☆	Principe des tiroirs · Récurrence et constructions récursives
2010 C5	★★★☆☆	Double comptage
2006 C5	★★★☆☆	Récurrence et constructions récursives
2025 C6	★★★★☆	Principe extrémal · Double comptage
2022 C8 · OIM P6	★★★★☆	Double comptage
2020 C6 · OIM P3	★★★★☆	Principe extrémal
2019 C8	★★★★☆	-
2016 C6	★★★★☆	Invariants et monovariants
2013 C6	★★★★☆	Principe extrémal · Principe des tiroirs
2010 N6	★★★★☆	Valuations p-adiques et lemme LTE · Suites et récurrences
2007 C6 · OIM P3	★★★★☆	Invariants et monovariants
2025 C8 · OIM P6	★★★★★	Coloriages et pavages · Principe extrémal · Double comptage · AM-GM et moyennes
2024 N7	★★★★★	Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Valuations p-adiques et lemme LTE
2024 C8	★★★★★	Récurrence et constructions récursives · Coloriages et pavages · Principe extrémal
2023 C7	★★★★★	Principe extrémal
2018 C7	★★★★★	Double comptage · Coloriages et pavages
2017 G8	★★★★★	Invariants et monovariants · Double comptage
2016 C8	★★★★★	Coloriages et pavages · Principe des tiroirs
2015 C7	★★★★★	Coloriages et pavages · Principe extrémal · Récurrence et constructions récursives
2014 C9	★★★★★	Invariants et monovariants · Double comptage
2012 C7	★★★★★	Principe des tiroirs · Récurrence et constructions récursives
2011 N8	★★★★★	Ordre d'un élément et racines primitives · Résidus quadratiques
2010 C7	★★★★★	Théorème des restes chinois · Récurrence et constructions récursives
2006 C7	★★★★★	Géométrie combinatoire : enveloppe convexe, points du réseau