Université de Liège Année académique 2022 – 2023

Théorie des graphes

Exercices 1
Sciences Mathématiques (blocs 2 et 3)
Sciences Informatiques (bloc 2)
Titulaire : Michel Rigo Assistant : Antoine Renard
[email protected] [email protected]

1 Manipulations de base
Exercice 1.1. Il existe quatre groupes sanguins :
— AB pour les personnes ayant des antigènes A et B,
— A pour les personnes ayant des antigènes A mais pas d’antigènes B,
— B pour les personnes ayant des antigènes B mais pas d’antigènes A,
— O pour les personnes n’ayant ni d’antigènes A ni d’antigènes B.
Il existe également deux rhésus sanguins :
— positif (+),
— négatif (−).
On admet que les seuls interdits biologiques pour recevoir du sang sont les suivants :
— recevoir du sang possédant un antigène dont on est dépourvu,
— recevoir du sang ayant un rhésus positif si on est rhésus négatif.
A partir des informations données ci-dessus,
(a) tracer le graphe orienté dont {AB+, AB−, A+, A−, B+, B−, O+, O−} est l’ensemble des som-
mets et dont les arcs désignent les possibilités de donner du sang sans violer les interdits biolo-
giques,
(b) donner le demi-degré sortant d+ (v) et le demi-degré entrant d− (v) de chaque nœud v, et en
déduire le groupe sanguin qui est donneur (resp. receveur) universel,
(c) donner l’ensemble des successeurs succ(v) et l’ensemble des prédécesseurs pred(v) de chaque
nœud v.

Exercice 1.2. Un fermier se promène avec trois êtres vivants : un loup, une chèvre et une salade. Il
doit traverser une rivière mais il ne peut le faire qu’avec au plus un seul des trois à la fois. De plus, le
fermier ne peut quitter une rive en y laissant la chèvre, sauf si celle-ci y reste seule (sinon, en l’absence
du fermier, la chèvre mangerait la salade ou serait mangée par le loup). À l’aide d’un graphe non
orienté et simple, expliquer comment le fermier peut s’y prendre pour se retrouver sur l’autre rive en
le moins de traversées possible.

Exercice 1.3. Lors d’une réception dans laquelle il y a au moins deux personnes, toutes les personnes
qui se connaissent se sont serrées la main. Montrer qu’il existe deux personnes qui ont serré la main
au même nombre de personnes.

Exercice 1.4. À une réception, n couples sont invités (n ≥ 1). Certains invités se serrent la main, mais
personne ne sert la main à son conjoint. L’un des invités, nommé I, demande à chaque autre personne
combien de poignées de main elle a données. Il obtient 2n − 1 réponses différentes. Combien la femme
de monsieur I a-t-elle donné de poignées de main ? Combien monsieur I a-t-il donné de poignées de
main ?

1. Par convention, tous les graphes de ces notes sont supposés finis.

1
Théorie des graphes 2022 – 2023

Exercice 1.5.
(a) Construire le graphe biparti complet K2,3 et compter son nombre d’arêtes.
(b) Combien le graphe biparti complet Km,n possède-t-il d’arêtes ? (m, n ≥ 1)
(c) Construire le graphe triparti complet K2,3,2 et compter son nombre d’arêtes.
(d) Combien le graphe triparti complet Kl,m,n, possède-t-il d’arêtes ? (l, m, n ≥ 1)
Exercice 1.6. Prouver que les graphes non orientés suivants n’existent pas.
(a) Un graphe simple qui est 3-régulier (c’est-à-dire dont chaque nœud est de degré 3) et qui
possède exactement 7 nœuds. (Juin 2007, question 0a)
(b) Un graphe ayant un nombre impair de nœuds, tous de degré impair. (Juin 2006, question 1a)
(c) Un graphe simple ayant 8 nœuds et 29 arêtes. (Juin 2006, question 1b)
Exercice 1.7. Pour chacun des graphes simples non orientés suivants, donner un exemple d’existence
ou prouver l’inexistence.
(a) Un graphe biparti 3-régulier de 8 nœuds.
(b) Un graphe biparti 4-régulier de 11 nœuds.
Exercice 1.8.
(a) Existe-t-il un groupe de 11 personnes tel que chaque membre du groupe connaisse exactement
3 autres personnes de ce groupe ?
(b) Même question mais avec un groupe de 8 personnes (et chaque membre du groupe connaît
exactement 3 autres membres du groupe).
Pour les deux points précédents, en cas de réponse affirmative, représenter un graphe illustrant la
situation. Le graphe obtenu est-il toujours connexe ? (Août 2015, question 1)
Exercice 1.9. Soit G un graphe simple non orienté possédant m arêtes e1 , . . . , em . On définit le graphe
ligne L(G) comme le graphe ayant m sommets v1 , . . . , vm et l’arête {vi , vj } appartient à L(G) si et
seulement si les arêtes ei et ej de G sont adjacentes (i.e., ont une extrémité commune).
(a) Représenter le graphe ligne du graphe complet K4 , du graphe biparti complet K2,3 et d’un
cycle à 6 sommets.
(b) Donner une expression pour le nombre d’arêtes de L(G) en fonction des degrés des sommets
de G.
(c) Montrer que si G est un graphe simple k-régulier (i.e., chaque sommet est de degré k), alors
L(G) est (2k − 2)-régulier.
(Août 2015, question 3)
Exercice 1.10. Un tournoi est un graphe simple et orienté G = (V, E) tel que pour toute paire {u, v}
de sommets distincts, exactement l’un des deux arcs (u, v) ou (v, u) appartient à E. Un tournoi est
transitif si, pour tous sommets u, v, w, si (u, v) ∈ E et (v, w) ∈ E, alors (u, w) ∈ E. Un roi d’un tournoi
est sommet r à partir duquel on peut atteindre tout autre sommet de V par un chemin de longueur
au plus 2.
(a) Donner un exemple de tournoi transitif et un exemple de tournoi non transitif, tous deux avec
4 sommets. Dans chaque cas, exhiber un roi du tournoi.
(b Soit v un sommet d’un tournoi G = (V, E). Comparer d+ (v) + d− (v) et #V .
(c) Démontrer qu’un tournoi est transitif si et seulement s’il est sans cycle.
(d) Démontrer qu’un tournoi possède au moins un roi (indice : considérer un sommet r de demi-
degré sortant maximum et les ensembles succ(r) et pred(r)).
(Janvier 2016, question 1)
Exercice 1.11. Soit G un graphe simple ayant n sommets et n − 1 arêtes qui n’est pas un arbre. On
suppose qu’un sommet isolé est un arbre "trivial".
(a) Prouver que G n’est pas connexe
(b) Prouve que G possède une composante qui est un arbre.
(c) Prouver que G possède une composante qui n’est pas un arbre.
(d) Prouver que si G possède exactement deux composantes connexes, alors celle qui n’est pas un
arbre possède exactement un cycle.
(Janvier 2017, question 1)

2
Théorie des graphes 2022 – 2023

Exercice 1.12. Un matching parfait d’un graphe simple (non-orienté) G = (V, E) est un sous-ensemble
M ⊆ E tel que tout sommet de V est l’extrémité d’exactement une arête de M .
(a) Montrer que Kn possède un matching parfait si et seulement si n est pair.
(b) Combien de matchings parfaits distincts peut-on trouver dans le graphe biparti complet K3,3 ?
(c) Prouver qu’un arbre A a un matching parfait si et seulement si, pour chaque sommet v de A,
le graphe A − v possède une seule composante connexe ayant un nombre impair de sommets.
(d) On considère un jeu entre deux joueurs A et B. On donne un graphe simple connexe G. Le
joueur A débute la partie en choisissant un sommet. Les deux joueurs jouent alternativement en
choisissant un sommet non choisi précédemment avec la contrainte de choisir un sommet voisin
du dernier sommet sélectionné par l’autre joueur (autrement dit, A et B construisent ensemble
un chemin). Le premier joueur incapable de jouer (il n’y a plus de sommet valide disponible)
perd la partie. Montrer que si G a un matching parfait, alors B dispose d’une stratégie gagnante
(quels que soient les sommets choisis par A, B pourra toujours gagner).
(Août 2017, question 1)

Exercice 1.13. Soit G = (V, E) un graphe non orienté et non connexe. Montrer que son complémen-
taire, le graphe G = (V, (V × V )\E) est connexe. Que peut-on dire de diam(G) ?

Exercice 1.14. Soit k un nombre entier strictement positif. Soit G un graphe simple, non orienté,
connexe, fini et d’au moins deux nœuds. On suppose que dans chaque triplet de nœuds de G, on peut
toujours choisir deux nœuds dont la distance est inférieure ou égale à k. Prouver qu’il est possible de
colorier les nœuds de G avec deux couleurs, rouge et bleu, de manière à ce que les deux conditions
suivantes soient satisfaites simultanément :
— la distance entre deux nœuds rouges est toujours inférieure ou égale à 2k,
— la distance entre deux nœuds bleus est toujours inférieure ou égale à 2k.

Exercice 1.15. On considère un graphe simple non orienté de 7 nœuds, tous de degré supérieur ou
égal à 3.
(a) Prouver que ce graphe est connexe.
(b) Prouver que ce graphe n’a pas ses sept nœuds de degré exactement 3.

Exercice 1.16. Par définition, le rayon rad(G) d’un graphe G = (V, E) non orienté connexe non vide
est
rad(G) = min max d(a, b).
a∈V b∈V

(a) Montrer que tout graphe non orienté connexe non vide G vérifie les inégalités suivantes :

rad(G) ≤ diam(G) ≤ 2rad(G).

(b) Pour quelles valeurs de n ≥ 1 existe-t-il un graphe non orienté connexe qui possède n nœuds
et dont le diamètre vaut exactement le rayon ?
(c) Pour quelles valeurs de n ≥ 1 existe-t-il un graphe non orienté connexe qui possède n nœuds
et dont le diamètre vaut le double du rayon ?

Exercice 1.17. Soit G = (V, E) un graphe non orienté connexe non vide. Soit k = maxx∈V deg(x).
Prouver l’implication
k(k − 1)rad(G)
k ≥ 3 ⇒ #V < .
k−2
Exercice 1.18. Soit G = (V, E) un graphe simple non orienté non vide. Soit k = minx∈V deg(x).
(a) Prouver que G possède un chemin simple de longueur k.
(b) Prouver que G possède un circuit simple de longueur au moins k + 1 si k vaut au moins 2.

Exercice 1.19. Soit G un graphe non orienté connexe qui possède au moins un circuit simple de
longueur non nulle. On désigne par f (G) la longueur du plus petit circuit simple de longueur non nulle
de G.
(a) Prouver que f (G) ≤ 2 diam(G) + 1.
(b) Trouver un exemple réalisant l’égalité f (G) = 2 diam(G) + 1.

3
Théorie des graphes 2022 – 2023

Exercice 1.20. Un groupe d’amis organise une randonnée dans les Alpes. On a représenté par le graphe
ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer. Une arête entre deux
sommets coïncide avec l’existence d’un chemin entre les deux sommets. Les distances en kilomètres
entre chaque sommet sont indiquées sur le graphe. S’ils se trouvent au sommet B et souhaitent se
rendre au sommet N, pouvez-vous leur indiquer un chemin dans le graphe qui minimise la distance du
trajet ?

Exercice 1.21. Une agence de voyages organise différentes excursions dans une région du monde et
propose la visite de sites incontournables, nommés A, B, C, D, E et F. Ces excursions sont résumées
sur le graphe ci-dessous dont les sommets désignent les sites, les arêtes représentent les routes pouvant
être empruntées pour relier deux sites et le poids des arêtes désigne le temps de transport en heures
entre chaque site. Un touriste désire aller du site A au site F en limitant au maximum les temps de
transport.
(a) En utilisant un algorithme, déterminer la plus courte chaîne reliant le sommet A au sommet F.
(b) En déduire le temps de transport minimal pour aller du site A au site F.

Exercice 1.22. Appliquer l’algorithme de Dijkstra permettant d’obtenir un chemin de poids minimal
du sommet 1 vers les autres sommets du graphe. On considérera les itérations successives de l’algorithme
en fournissant les valeurs des variables T (v) et C(v) pour chaque sommet v ̸= 1 (poids actuel et chemin
réalisé pour le sommet v).

(Août 2016, question 1)

4
Théorie des graphes 2022 – 2023

Exercice 1.23. Appliquer l’algorithme de Dijkstra (en rappelant la signification des variables utilisées)
au graphe ci-dessous pour obtenir des chemins de poids minimal du sommet 0 vers les autres sommets.

(Août 2017, question 3)

Exercice 1.24. On considère les quinze dominos {i, j} où i et j sont des entiers vérifiant 0 < i < j < 7.
Est-il possible de juxtaposer ces dominos sur une ligne en respectant la règle principale de tout bon
jeu de dominos qui se respecte ? Si oui, dessiner un exemple. Si non, expliquer pourquoi.

Exercice 1.25.
(a) Parmi les trois graphes non orientés suivants, lesquels sont eulériens ?
(b) Parmi ceux qui ne le sont pas, lesquels possèdent néanmoins un chemin eulérien ? Déterminer
le nombre de chemins eulériens de chacun d’entre eux.

Exercice 1.26. Prouver qu’il n’existe pas de 1-graphe G = (V, E) non orienté, non connexe, de 2006
nœuds, qui est eulérien et dont le complémentaire G = (V, (V × V )\E) est également eulérien.
(Juin 2006, question 1c)

Exercice 1.27. On considère un 1-graphe G = (V, E) non orienté non connexe possédant n nœuds,
n étant un entier au moins égal à 3. On suppose que chaque composante connexe de G est un graphe
eulérien. Pour quelles valeurs de n le graphe G = (V, (V × V )\E) est-il eulérien ?

Exercice 1.28. Trouver toutes les valeurs entières de a, b, c telles que 0 < a ≤ b ≤ c et que le graphe
triparti complet Ka,b,c possède un chemin eulérien mais pas de circuit eulérien.

5
Théorie des graphes 2022 – 2023

Exercice 1.29. Trouver les composantes simplement connexes et fortement connexes du graphe orienté
suivant, et dessiner le graphe acyclique des composantes correspondant.

Exercice 1.30. Prouver qu’il n’existe pas de graphe G non orienté connexe possédant une et une seule
arête de coupure e et tel qu’une composante connexe du sous-graphe G − {e} possède au moins une
arête de coupure.
(Juin 2006, question 1d)

Exercice 1.31. On considère un graphe non orienté connexe G = (V, E), deux nœuds a et b, et une
partie S de V \{a, b} séparant a et b. Montrer qu’aucun sous-ensemble propre de S ne sépare a et b si
et seulement si tout point de S possède un voisin dans la composante connexe de G − S à laquelle a
appartient et un voisin dans la composante connexe de G − S à laquelle b appartient.

Exercice 1.32. On considère un graphe non orienté connexe G = (V, E), deux nœuds a et b, et une
partie S de V \{a, b} séparant a et b. On note Ca la composante connexe de a dans G − S et Cb la
composante connexe de b dans G − S. On considère une autre partie S ′ de V \{a, b} séparant a et b.
On note Ca′ et Cb′ les composantes connexes respectivement de a et de b dans G − S ′ . Montrer que les
ensembles X et Y définis par

X = (S ∩ Ca′ ) ∪ (S ∩ S ′ ) ∪ (S ′ ∩ Ca )
Y = (S ∩ Cb′ ) ∪ (S ∩ S ′ ) ∪ (S ′ ∩ Cb )

séparent a et b.

Exercice 1.33. Construire un graphe simple, non orienté et 3-régulier possédant une arête de coupure.
Déterminer le nombre minimum de sommets qu’un tel graphe possède (justifier votre réponse).
(Janvier 2015, question 1)

Définition 1.1. Deux graphes non orientés G1 = (V1 , E1 ) et G2 = (V2 , E2 ) sont isomorphes s’il
existe (au moins) une bijection f : V1 → V2 telle que {x, y} ∈ E1 ⇔ {f (x), f (y)} ∈ E2 .

Exercice 1.34. Montrer que sur tout ensemble de graphes, la relation binaire G1 est isomorphe à G2
est une relation d’équivalence.

6
Théorie des graphes 2022 – 2023

Exercice 1.35. Regrouper par classe d’isomorphie les huit graphes non orientés suivants.

Exercice 1.36. Trouver tous les graphes simples non orientés eulériens de 5 nœuds, à isomorphisme
près.

Exercice 1.37. Déterminer, à isomorphisme près, tous les graphes non orientés
(a) ayant 4 nœuds, tous de degré 1,
(b) ayant 5 nœuds, tous de degré 2,
(c) complets et dont le nombre d’arêtes est un multiple du nombre de nœuds,
(d) bipartis complets ayant exactement 12 arêtes.

Exercice 1.38.
(a) Combien le graphe non orienté ci-dessous possède-t-il de sous-graphes connexes non orientés ?
(b) Combien le graphe non orienté ci-dessous possède-t-il de sous-graphes connexes non orientés,
à isomorphisme près ?

Exercice 1.39. Trouver tous les arbres, à isomorphisme près, ayant exactement
(a) 6 nœuds,
(b) 7 nœuds,
(c) 8 nœuds.

7
Théorie des graphes 2022 – 2023

Exercice 1.40. Soit n un entier supérieur ou égal à 4. Trouver combien d’arbres de n nœuds sont de
diamètre égal à 2 (resp. 3), à isomorphisme près.

Exercice 1.41. Soient k et n des entiers strictement positifs. Trouver le nombre d’arêtes et la somme
des degrés des nœuds d’une forêt de k arbres et n nœuds.

Exercice 1.42. Trouver tous les arbres dont le complémentaire n’est pas connexe.

Exercice 1.43. Trouver le nombre de sous-arbres couvrants du graphe non orienté ci-dessous.

Exercice 1.44. Soit G = (V, E) un arbre de diamètre k ≥ 1.

 k nœuds u et v tels que deg(u) = deg(v) = 1 et que d(u, v) = k.
(a) Prouver qu’il existe deux
(b) Prouver que rad(G) = 2 .
(Interro 22/03/2007)

Exercice 1.45. On considère un arbre fini non orienté G et deux de ses sous-arbres A et B ayant au
moins un sommet commun. Le sous-graphe (A ∩ B) de G, constitué des nœuds communs et des arêtes
communes de A et de B, est-il nécessairement un arbre ?
(Août 2009, question 2)

Exercice 1.46. Soient d un nombre entier strictement positif et G l’ensemble des graphes (finis) non
orientés connexes de diamètre d (on travaille à isomorphisme près). Déterminer la valeur suivante

max min{diam(T) : T est un arbre de recouvrement de G}.

G∈G

Exercice 1.47. Construire deux arbres non isomorphes ayant chacun 12 sommets dont 3 exactement
sont de degré 3 et un unique sommet de degré 2.
(Août 2016, question 3)

Exercice 1.48. Sachant que h : {1, 2, 3, 4, 5} → {1, 2, 3, 4, 5} est un automorphisme sur le graphe
orienté dessiné ci-dessous, décrire explicitement h. Il est nécessaire de décrire toutes les solutions
possibles.

8
Théorie des graphes 2022 – 2023

Exercice 1.49. Trouver le nombre d’automorphismes de chacun des trois graphes suivants.

Exercice 1.50. Soient m et n deux entiers strictement supérieurs à 2. On nomme G et H deux graphes
non orientés en forme de polygone de respectivement m et n côtés. Pour quelles valeurs de m et de n
existe-t-il un homomorphisme du graphe G sur le graphe H ?
Exercice 1.51. Dessiner trois graphes simples non orientés deux à deux non isomorphes qui possèdent
chacun exactement 20 automorphismes.
(Juin 2008, question 1)
Exercice 1.52. Décrire un graphe fini simple orienté ayant exactement 2009 automorphismes.
(a) Avec le nombre d’arcs que vous voulez.
(b) Avec au plus 90 arcs.
(c) Avec au plus 62 arcs.
Exercice 1.53. Pour quelles valeurs du nombre entier naturel n existe-t-il un graphe simple orienté
ayant exactement n automorphismes ? Même question dans le cas de graphes non orientés.
Exercice 1.54. Trouver la fermeture du graphe non orienté suivant.

Exercice 1.55. Quel est le nombre maximum d’arêtes que peut posséder un graphe simple non orienté
non complet mais égal à sa fermeture ? La réponse sera donnée en fonction du nombre de nœuds du
graphe.
Exercice 1.56. Pour chacun des graphes simples non orientés suivants, donner un exemple d’existence
ou prouver l’inexistence.
(a) Un graphe eulérien et non hamiltonien.
(b) Un graphe hamiltonien d’au moins 3 nœuds et avec une arête de coupure.
Exercice 1.57. Démontrer que le graphe biparti complet Km,n est hamiltonien si et seulement si
m = n.
(Août 2016, question 2)

9
Théorie des graphes 2022 – 2023

Exercice 1.58. Trente et un étudiants désirent se réunir une fois par jour autour d’une table ronde.
Aucun d’entre eux n’accepte d’avoir le même voisin plus d’une fois. Combien de jours au maximum
peuvent-ils se réunir ?
(Juin 2008, question 2)
Exercice 1.59. On considère le graphe qui est simple, orienté, qui a exactement 12 nœuds notés
v0 , v1 , v2 , . . . , v11 et qui est tel qu’il existe un arc partant du nœud vi et arrivant au nœud vj si et
seulement si j ≡ i + 3 (mod 12) ou j ≡ i + 4 (mod 12).
(a) Prouver que ce graphe est fortement connexe.
(b) Ce graphe est-il eulérien ?
(c) Quel est le nœud à partir duquel il est nécessaire d’emprunter le plus d’arcs pour atteindre le
nœud v0 ?
(d) Prouver que ce graphe n’est pas hamiltonien.
(Juin 2007, question 1)
Exercice 1.60. On considère un graphe simple, orienté, de 30 nœuds notés v0 , v1 , v2 , . . . , v29 et tel
qu’il existe un arc partant du nœud vi et arrivant au nœud vj si et seulement si il existe k ∈ {6, 15}
tel que j ≡ i + k (mod 30). On note G ce graphe et H sa composante fortement connexe à laquelle le
nœud v0 appartient.
(a) Montrer que le graphe G possède trois composantes fortement connexes.
(b) Le graphe H est-il eulérien ?
(c) Le graphe H est-il hamiltonien ?
(d) Calculer la valeur du diamètre du graphe H.
(e) Combien le graphe H possède-t-il d’automorphismes ?
(Août 2008, question 1)
Exercice 1.61. Soit n un entier supérieur ou égal à 3. Quel est, en fonction de n, le nombre maximum
d’arêtes que peut avoir un graphe simple non orienté non hamiltonien de n nœuds ? Justifier.
Exercice 1.62. Soit G = (V, E) un graphe simple non orienté connexe tel que #V ≥ 3. Notons G
le graphe complémentaire de G. Prouver que si G n’a pas de sous-graphe triangulaire, alors G a un
chemin hamiltonien.
Exercice 1.63. Lesquels des quatre graphes suivants sont hamiltoniens ?

(a)

(b)

10
Théorie des graphes 2022 – 2023

(c) Il s’agit du graphe non orienté dont l’ensemble des nœuds est {0, 1, 2}3 et pour lequel le nœud
x = (x1 , x2 , x3 ) et le nœud y = (y1 , y2 , y3 ) sont reliés par une arête si et seulement si deux des
trois nombres |x1 − y1 |,|x2 − y2 | et |x3 − y3 | sont nuls et que le troisième vaut 1.

(d) Il s’agit du graphe de Petersen.

2 Étude algébrique
Exercice 2.1. En respectant la numérotation des sommets, écrire la matrice d’adjacence des deux
multi-graphes suivants, le premier étant non orienté, et le second étant orienté.

Exercice 2.2. Prouver qu’il n’existe pas de graphe simple non orienté dont la matrice d’adjacence
(pour une numérotation quelconque des nœuds) possède une ligne qui n’est la transposée d’aucune de
ses colonnes.
(Juin 2007, question 0b)

Exercice 2.3.
(a) Écrire la matrice d’adjacence d’un graphe non orienté en forme de carré (pour une numérotation
quelconque de ses nœuds) et trouver son polynôme caractéristique.
(b) Écrire la matrice d’adjacence du graphe Kn (pour une numérotation quelconque de ses nœuds)
et trouver son polynôme caractéristique.

11
Théorie des graphes 2022 – 2023

Exercice 2.4. Trouver le plus directement possible le polynôme caractéristique du graphe non orienté
suivant.

Exercice 2.5. À isomorphisme près, trouver tous les graphes simples non orientés ayant un polynôme
caractéristique de la forme λ4 + aλ2 − 4λ + b où a et b sont des nombres entiers.

Exercice 2.6. Prouver qu’il n’existe pas de graphe simple non orienté connexe ayant un polynôme
caractéristique de la forme λ6 − 6λ4 − 4λ3 + aλ2 + bλ + c où a, b et c sont des nombres entiers.

Exercice 2.7. On considère un graphe simple non orienté non complet ayant un polynôme caractéris-
tique de la forme −λ7 + xλ5 + aλ4 + bλ3 + cλ2 + dλ + e où a, b, c, d, e et x sont des nombres entiers.
Quelles valeurs extrêmes x peut-il atteindre ?

Exercice 2.8. On considère le graphe K3 . On note A et B deux de ses nœuds (distincts). Trouver,
au moyen de la matrice d’adjacence du graphe, le nombre de chemins de longueur n partant du nœud
A et arrivant au nœud B.

Exercice 2.9. Trouver, au moyen de sa matrice d’adjacence, le nombre de chemins fermés de longueur
k du graphe complet Kn .

Exercice 2.10. On considère le graphe biparti complet K3,3 .

(a) Prouver que 0 est une valeur propre de multiplicité 4 de ce graphe.
(b) Prouver que 3 est la plus grande valeur propre de ce graphe.
(c) Prouver que −3 est une valeur propre de ce graphe.
(d) Prouver que si les valeurs propres de ce graphe sont λ1 , λ2 , λ3 , λ4 , λ5 , λ6 , alors le nombre de
chemins fermés de longueur n (n ≥ 1) partant d’un sommet donné de ce graphe est (λn1 + λn2 +
λn3 + λn4 + λn5 + λn6 )/6.
(e) Déterminer exactement le nombre de chemins ouverts de longueur 8 partant d’un sommet donné
de ce graphe.
Suggestion : De simples arguments théoriques peuvent suffire et éviter des calculs aux points a,b,c.
Rappel : Un chemin (v0 , v1 , . . . , vn ) de longueur n (n ≥ 1) est fermé si v0 = vn et ouvert si v0 ̸= vn .
(Juin 2006, question 2)

Exercice 2.11.
(a) Trouver le nombre de chemins de longueur 8 du graphe simple non orienté triparti complet
K2,2,2 .
(b) Trouver le nombre de chemins fermés de longueur n (n ≥ 1) du graphe simple non orienté
triparti complet K2,2,2 .

Exercice 2.12. On considère le graphe non orienté biparti complet Ka,b où a et b sont deux nombres
entiers strictement positifs.
(a) Combien existe-t-il d’automorphisme(s) sur ce graphe ?
(b) Si on note λ1 , λ2 , . . . , λa+b les valeurs propres de ce graphe, prouver qu’il possède exactement
λn1 + λn2 + · · · + λna+b chemins fermés de longueur n (n ≥ 1).
(c) Prouver que 0 est une valeur propre de ce graphe si a + b > 2, et déterminer sa multiplicité.
(d) Déterminer le nombre de chemins fermés de longueur 1 et le nombre de chemins fermés de
longueur 2 de ce graphe, puis les dernières valeurs propres de ce graphe.

12
Théorie des graphes 2022 – 2023

Exercice 2.13. Soit n un entier strictement positif. On considère le graphe simple non orienté triparti
complet Kn,n,n . On note A la matrice d’adjacence de ce graphe (pour une numérotation quelconque
de ses sommets).
(a) Que vaut la somme des multiplicités algébriques des valeurs propres non nulles de la matrice
A?
(b) Calculer la somme des (3n) valeurs propres de la matrice A.
(c) Calculer la somme des carrés des (3n) valeurs propres de la matrice A.
(d) Calculer la somme des cubes des (3n) valeurs propres de la matrice A.
(e) Déterminer toutes les valeurs propres de la matrice A.
Remarque : L’ordre des réponses aux points (a), (b), (c), (d), (e) est libre. Obtenir la réponse du point
(e) rend les autres points très faciles à traiter, mais il est probablement globalement plus simple de
déduire la réponse du point (e) à partir des réponses des quatre autres points.
(Août 2008, question 2)

Exercice 2.14. Soit n un paramètre entier strictement positif, en fonction duquel les réponses doivent
être discutées. Soit C2n un ensemble de n arêtes, deux à deux sans sommet commun, du graphe non
orienté complet K2n . Soit Gn le graphe défini, à isomorphisme près, par Gn = K2n − C2n .
(a) Combien le graphe Gn possède-t-il d’automorphismes ? Combien de composantes connexes le
graphe Gn possède-t-il ? Est-il eulérien ? Est-il hamiltonien ?
(b) Trouver les valeurs propres du graphe Gn avec leur multiplicité.

Exercice 2.15. Soit n un paramètre entier strictement positif, en fonction duquel les réponses doivent
être discutées. Soit C3n l’ensemble des arêtes de n sous-graphes triangulaires disjoints du graphe non
orienté complet K3n . Soit Gn le graphe défini par Gn = K3n − C3n .
(a) Trouver toutes les valeurs propres du graphe Gn avec leur multiplicité.
(b) Combien le graphe Gn possède-t-il d’automorphismes ?
(c) Le graphe Gn est-il hamiltonien ?
(Mai 2009, questions 1A, 1Ba, 1Bb)

Exercice 2.16. Soit n un paramètre entier strictement positif, en fonction duquel les réponses doivent
être discutées. Soit C4n l’ensemble des arêtes de n sous-graphes, isomorphes au graphe complet K4 et
deux à deux disjoints, du graphe non orienté complet K4n . Soit Gn le graphe défini par Gn = K4n −C4n .
Pour n > 1, le graphe Gn est donc isomorphe au graphe n-parti complet K4, . . . , 4 .
| {z }
n indices
(a) Combien le graphe Gn possède-t-il d’arêtes ?
(b) Le graphe Gn est-il hamiltonien ?
(c) Trouver toutes les valeurs propres du graphe Gn avec leur multiplicité.
(Août 2009, questions 1a, 1b, 1e)

Exercice 2.17. Soient k et n deux entiers strictement positifs. On considère un graphe simple non
orienté k-régulier de n nœuds pour lequel il existe toujours un et un seul chemin de longueur inférieure
ou égale à 2 entre deux nœuds distincts. On note A la matrice d’adjacence de ce graphe (pour une
numérotation quelconque de ses sommets).
(a) Donner la plus grande valeur propre de la matrice A et un des vecteurs propres relatifs à cette
valeur propre.
(b) Prouver que tous les éléments de la matrice A2 + A + (1 − k)I sont des 1.
(c) Prouver qu’un graphe vérifiant les conditions de l’énoncé ne peut exister que si n = k 2 + 1.
(d) Dessiner un graphe vérifiant les conditions de l’énoncé pour (k, n) = (3, 10).
(Juin 2007, question 2)

13
Théorie des graphes 2022 – 2023

Exercice 2.18. Soient k et n deux entiers strictement positifs. On considère un graphe simple non
orienté k-régulier de n nœuds pour lequel il existe toujours un et un seul chemin simple de longueur
inférieure ou égale à 3 entre deux nœuds distincts. On note A la matrice d’adjacence de ce graphe
(pour une numérotation quelconque de ses sommets).
(a) Dessiner un graphe vérifiant les conditions de l’énoncé pour (k, n) = (2, 7).
(b) Quelle est, en fonction de k, la plus grande valeur propre de la matrice A ?
(c) Prouver que chaque ligne de la matrice A3 +A2 +A+(1−k)I possède exactement k composantes
égales à 2k et (n − k) composantes égales à 1.
(d) Prouver qu’un graphe vérifiant les conditions de l’énoncé ne peut exister que si n = k 3 − k 2 +
k + 1.
(e) Dans un graphe vérifiant les conditions de l’énoncé pour k = 10, quelle est, en moyenne, la
distance entre les deux extrêmités d’un chemin de longueur 4 ?
(a,b,c,d (mais pas e) : Juin 2008, question 3)

Exercice 2.19. On considère le graphe de Petersen et sa matrice d’adjacence A (pour une numérota-
tion quelconque des sommets de ce graphe).
(a) Donner la plus grande valeur propre de la matrice A, ainsi qu’un de ses vecteurs propres.
(b) Démontrer que toutes les coordonnées de la matrice A2 + A − 2I sont égales à 1.
(c) Diagonaliser la matrice A2 + A − 2I et en déduire que chaque valeur propre de la matrice A
appartient à l’ensemble {−2, 1, 3}.
(d) Déterminer la multiplicité de chaque valeur propre de la matrice A.
(e) Déterminer le nombre de chemins fermés de longueur 100 du graphe de Petersen.

Exercice 2.20. Parmi les cinq graphes suivants (un seul est non orienté), lesquels ont une matrice
d’adjacence qui est irréductible ? Lesquels en ont une qui est primitive ?

14
Théorie des graphes 2022 – 2023

Exercice 2.21. On considère le graphe orienté suivant. On demande d’évaluer le plus rapidement
possible, à un constante multiplicative (strictement positive) près, le comportement asymptotique du
nombre de chemins de longueur n joignant le sommet A au sommet B (lorsque n tend vers l’infini).

Exercice 2.22.
(a) Trouver le nombre de sous-arbres couvrants du multi-graphe non orienté suivant.
(b) Le nombre de sous-arbres couvrants changerait-il si on rajoutait des boucles sur certains
nœuds ?

15
Théorie des graphes 2022 – 2023

Exercice 2.23. Trouver le nombre de sous-arbres couvrants du graphe biparti complet K3,3 .
Exercice 2.24. On considère la matrice
 
1 0 1 0
0 0 0 1
M =
1

0 0 1
0 1 0 1

(a) Représenter le graphe orienté D ayant M comme matrice d’adjacence.

(b) Déterminer les composantes fortement connexes du graphe D.
(c) Renuméroter les sommets de D de telle sorte que la matrice d’adjacence correspondante soit
bloc-triangulaire composée (supérieure ou inférieure).
(d) Déterminer les valeurs propres de D. Exprimer, en fonction de celles-ci, le nombre de chemins
fermés de longueur n dans D.
(e) Prouver que la matrice M n’est ni primitive, ni irréductible. Est-il possible de remplacer un
unique élément de la matrice M pour la rendre irréductible ? Si oui, énumérer toutes les possi-
bilités. Même question pour la rendre primitive.
(f) (BONUS) Si cn dénote le nombre de chemins de longueur n joignant les deux sommets de D
réalisant le diamètre de D, prouver que cn satisfait, pour tout n ≥ 0 la relation

cn+4 = 2 cn+3 + cn+2 − 2 cn+1 − cn .

(Janvier 2015, question 3)

Exercice 2.25. On considère la matrice
 
1 0 0 0
0 0 1 0
M =
1

0 0 1
0 1 0 1

(a) Représenter le graphe orienté D ayant M comme matrice d’adjacence.

(b) Déterminer les composantes fortement connexes du graphe D.
(c) Prouver que la matrice M n’est ni primitive, ni irréductible. Est-il possible d’ajouter un unique
arc au graphe D pour rendre la matrice correspondante irréductible ? Si oui, énumérer toutes
les possibilités. Même question pour la rendre primitive.
(d) En supposant les sommet de D numérotés de façon compatible avec M , montrer que, pour
tout n, les nombres de chemins de longueur n joignant 3 à 2, 4 à 3, 2 à 4 sont égaux. (Bonus :
montrer que cette quantité est aussi égale au nombre de chemins de longueur n joignant 2 à 1.)
(Janvier 2016, question 3)
Exercice 2.26. On considère la matrice
 
0 1 1 0
 0 0 1 0 
M =
 0
.
0 0 1 
1 0 0 0

(a) Représenter le graphe orienté D ayant M comme matrice d’adjacence.

(b) Prouver que la matrice M est primitive. Est-il possible de supprimer un unique arc au graphe
D pour rendre la matrice correspondante irréductible mais non primitive ?
(c) Soit α la valeur propre de Perron de M . Quels renseignements peut-on tirer de M n quand n
tend vers l’infini ? (Un énoncé théorique suffit pour répondre à la question.)
(d) En supposant les sommets de D numérotés de façon compatible avec M , montrer que, pour
tout n ≥ 4, le nombre de chemins fermés partant et arrivant en 1 de longueur n + 4 est égal
à la somme des nombres de chemins fermés partant et arrivant en 1 de longueur n et ceux de
longueur n + 1. En déduire le nombre de tels chemins fermés de longueur 16 passant par 1.
(Janvier 2017, question 3)

16
Théorie des graphes 2022 – 2023

3 Graphes planaires
Exercice 3.1. Regrouper par classe d’homéomorphie les onze graphes non orientés suivants, et préciser
lesquels sont planaires.

Exercice 3.2. Pour quelles valeurs de n ∈ N \ {0}, le graphe complet Kn est-il planaire ?

Exercice 3.3. (cf. Exercice 2.15) Le graphe Gn = K3n − C3n est-il planaire ?
(Mai 2009, question 1Bc)

Exercice 3.4. (cf. Exercice 2.16) Le graphe Gn = K4n − C4n est-il planaire ?
(Août 2009, question 1c)

Exercice 3.5. Prouver qu’il n’existe pas de graphe simple non orienté planaire qui possède exactement
6 nœuds dont 3 au moins sont de degré 5.
(Juin 2007, question 0c)

Exercice 3.6. Trouver le nombre maximum A d’arêtes qu’un graphe simple planaire de 6 nœuds peut
avoir ? Donner une représentation planaire d’un graphe de 6 nœuds et A arêtes.

Exercice 3.7. Prouver que les graphes simples non orientés suivants n’existent pas ou en dessiner une
représentation planaire.
(a) Un graphe planaire ayant exactement deux faces, toutes triangulaires.
(b) Un graphe planaire ayant exactement cinq faces, toutes triangulaires.
(c) Un graphe planaire ayant exactement six faces, toutes triangulaires. (Juin 2008, question 4)
(d) Un graphe planaire ayant exactement huit faces, toutes triangulaires.

Exercice 3.8.
(a) Est-il possible de numéroter les arêtes d’un octaèdre régulier de 1 à 12 de façon à ce que la
somme des numéros des arêtes aboutissant en un sommet soit indépendante du sommet choisi ?
(b) Est-il possible de numéroter les arêtes d’un cube de 1 à 12 de façon à ce que la somme des
numéros des arêtes aboutissant en un sommet soit indépendante du sommet choisi ?

17
Théorie des graphes 2022 – 2023

Exercice 3.9. On considère une représentation planaire d’un graphe ayant exactement 300 faces,
toutes triangulaires.
(a) Déterminer les nombres A d’arêtes et S de sommets de ce graphe.
(b) Comparer la somme des degrés des nœuds de ce graphe avec celle de son dual.
(c) Trouver la plus grande valeur de n pour laquelle il existe un graphe vérifiant l’énoncé et dont
le dual possède une face qui est un polygone ayant n côtés.
Exercice 3.10. Un ballon de football peut être vu comme un polyèdre convexe dont chaque face est
hexagonale ou pentagonale. Sachant que chaque sommet de ce polyèdre appartient à exactement deux
faces hexagonales et une face pentagonale, déterminer les nombres S de sommets, A d’arêtes, H de
faces hexagonales et P de faces pentagonales de ce polyèdre.
Exercice 3.11. On considère un polyèdre convexe qui a exactement six faces carrées et huit faces
triangulaires. Chaque sommet de ce polyèdre est le sommet du même nombre c de carrés et du même
nombre t de triangles. Trouver c, t, le nombre d’arêtes et le nombre de sommets de ce polyèdre.
Exercice 3.12. On considère un graphe et une de ses représentations planaires dont chaque sommet est
un sommet d’exactement une face triangulaire, deux faces carrées et une face pentagonale. Déterminer
le nombre de sommets S, le nombre d’arêtes A, le nombre de faces triangulaires T , le nombre de faces
carrées C et le nombre de faces pentagonales P de ce graphe.
(Juin 2006, question 3)
Exercice 3.13. On considère un graphe et une de ses représentations planaires dont chaque face est
triangulaire et possède un nœud de degré 3 et deux nœuds de degré 6. Déterminer le nombre N3 de
nœuds de degré 3, le nombre N6 de nœuds de degré 6, le nombre A d’arêtes et le nombre F de faces de
ce graphe, en justifiant soigneusement chaque mise en équation. Dessiner une représentation planaire
de ce graphe.
(Juin 2007, question 3)
Exercice 3.14. On considère une représentation planaire d’un graphe. Sachant que chaque face de
celle-ci est un quadrilatère ayant exactement un nœud de degré 3, deux nœuds de degré 4 et un nœud
de degré 5, touver son nombre d’arêtes.
(Juin 2008, question 5)
Exercice 3.15. On considère un graphe planaire dont les représentations planaires n’ont que des faces
pentagonales et dont celles de son dual n’ont que des faces triangulaires. Trouver le nombre de faces,
le nombre d’arêtes et le nombre de sommets de ce graphe et en dessiner une représentation planaire.
(Août 2008, question 3)
Exercice 3.16. On considère un graphe planaire dont les représentations planaires n’ont que des faces
triangulaires et dont celles de son dual n’ont que des faces quadrilatérales. Trouver le nombre de faces,
le nombre d’arêtes et le nombre de sommets de ce graphe et en dessiner une représentation planaire.
(Août 2009, question 3)
Exercice 3.17. On considère une représentation planaire A d’un graphe G qui est le squelette d’un
polyèdre convexe et une représentation planaire B du dual de G. Toutes les faces de A sont des octo-
gones ou des triangles. Toutes les faces de B sont des triangles dont exactement un nœud est de degré
strictement inférieur à 6. Trouver le nombre de sommets du graphe G et dessiner une représentation
planaire de ce dernier.
Exercice 3.18. On considère une représentation planaire R d’un graphe G qui est le squelette d’un
polyèdre convexe et une représentation planaire R ∗ du dual de G. On suppose que R et R ∗ ont le
même nombre de faces triangulaires et que toutes leurs autres faces sont quadrilatérales. Soient T, Q
et A les nombres respectifs de faces triangulaires, de faces quadrilatérales et d’arêtes du graphe R.
(a) Exprimer A en fonction de T et Q.
(b) Prouver que R et R ∗ ont le même nombre de faces quadrilatérales.
(c) Exprimer T et Q en fonction de A.
(d) Dessiner une représentation planaire dans le cas particulier T = Q = 4.
(Mai 2009, question 3)

18
Théorie des graphes 2022 – 2023

Exercice 3.19. On considère un graphe planaire connexe G ayant huit faces triangulaires et dix-huit
faces carrées. De chaque sommet de G partent une face triangulaire et trois faces carrées. Déterminer
le nombre de sommets et le nombre d’arêtes de G.
(Janvier 2016, question 4)

Exercice 3.20. On considère un graphe planaire connexe G ayant trente faces limitées par quatre
arêtes. De chaque sommet de G partent trois ou cinq faces. Déterminer le nombre total de sommets et
le nombre d’arêtes de G. Déterminer également le nombre de sommets de degré 3 et 5 respectivement.
(Août 2016, question 4)

Exercice 3.21. On considère un graphe planaire connexe G ayant 32 faces triangulaires et 6 faces
carrées. De chaque sommet de G partent quatre faces triangulaires et une face carrée. Déterminer le
nombre de sommets et le nombre d’arêtes de G.
(Janvier 2017, question 4)

Exercice 3.22. On considère un graphe planaire connexe G ayant 20 faces triangulaires et 12 faces
pentagonales. De chaque sommet de G partent deux faces triangulaires et deux faces pentagonales.
Déterminer le nombre de sommets et le nombre d’arêtes de G.
(Août 2017, question 4)

Exercice 3.23. (Solides de Platon) Un polyèdre est dit régulier si toutes ses faces sont des polygones
réguliers ayant le même nombre de côtés (autrement dit, les faces sont toutes identiques) et si de chacun
de ses sommets part le même nombre d’arêtes. Un solide de Platon est un polyèdre régulier convexe.
Démontrer qu’il n’y a que cinq solides de Platon : le tétraèdre régulier (ou pyramide), l’hexaèdre
régulier (ou cube), l’octaèdre régulier, le dodécaèdre régulier et l’icosaèdre régulier. Rechercher aussi
aussi les duaux de ces solides.

Exercice 3.24. On considère un polyèdre convexe de trente-deux faces, toutes triangulaires ou penta-
gonales. Chaque sommet de ce polyèdre rencontre le même nombre t de face(s) triangulaire(s) et le
même nombre p de face(s) pentagonale(s). Trouver les valeurs de t et de p, ainsi que les nombres
d’arêtes et de sommets de ce polyèdre.

Exercice 3.25. On considère un polyèdre convexe de trente-huit faces, toutes carrées ou triangulaires.
Chaque sommet de ce polyèdre rencontre le même nombre c de face(s) carrée(s) et le même nombre t
de face(s)triangulaire(s). Trouver les valeurs de c et de t, ainsi que les nombres d’arêtes et de sommets
de ce polyèdre.

4 Coloriages 2
Exercice 4.1.
(a) Peut-on colorier chaque arête du graphe K5 en rouge ou en bleu de façon à ne pas avoir de
sous-graphe triangulaire dont les trois arêtes sont de la même couleur ?
(b) Peut-on colorier chaque arête du graphe K6 en rouge ou en bleu de façon à ne pas avoir de
sous-graphe triangulaire dont les trois arêtes sont de la même couleur ?
(c) Peut-on colorier chaque arête du graphe K17 en rouge, en bleu ou en jaune de façon à ne pas
avoir de sous-graphe triangulaire dont les trois arêtes sont de la même couleur ?
(d) Trouver un nombre n pour lequel vous pouvez prouver qu’on ne peut pas colorier chaque arête
du graphe Kn en rouge, en bleu, en jaune ou en vert de façon à ne pas avoir de sous-graphe
triangulaire dont les trois arêtes sont de la même couleur.

2. Il ne s’agit que de graphes simples non orientés.

19
Théorie des graphes 2022 – 2023

Exercice 4.2. On considère un multi-graphe G non orienté et sans boucle. On se demande s’il est
possible de colorier ses arêtes avec deux couleurs, rouge et bleu, de façon à ce que chacun de ses nœuds
rencontre autant d’arêtes rouges que d’arêtes bleues.
(a) Prouver que cela n’est possible pour aucun multi-graphe G de 2009 arêtes.
(b) Prouver que cela est possible pour tout multi-graphe G de 12 arêtes, qui est connexe et dont
chacun des nœuds est de degré pair.
(c) Donner un exemple pour lequel c’est impossible malgré le fait que G a 12 arêtes et que chacun
de ses nœuds est de degré pair.
(d) Cela est-il possible pour tout multi-graphe G de 12 arêtes et dont chacun des nœuds est de
degré multiple de 4 ?
(Juin 2009, question 2)
Exercice 4.3. Soit n ≥ 1. Le n-cube Qn est un graphe défini comme suit. Ci-dessous, sont représentés
tout d’abord les graphes Q1 , Q2 et Q3 :

Pour tout n ≥ 1, on obtient Qn+1 en considérant deux copies disjointes de Qn et en ajoutant une arête
pour chaque paire de sommets qui se correspondent dans les deux copies de Qn . Voici une représentation
de Q4 :

(a) En fonction de n, combien de sommets et d’arêtes possède Qn ? Quel est le degré de chaque
sommet de Qn ?
(b) Pour quelles valeurs de n, le n-cube est-il hamiltonien ?
(c) Pour quelles valeurs de n, le n-cube est-il eulérien ?
(d) Prouver que, pour tout n ≥ 1, Qn est un graphe 2-colorable. En déduire que Qn est biparti.
(Janvier 2015, question 2)
Exercice 4.4. On considère le graphe de Petersen P = (V, E).

(a) Montrer que P contient un chemin hamiltonien.

(b) On considère le graphe obtenu en supprimant un sommet quelconque de P . Ce nouveau graphe
possède-t-il un circuit hamiltonien ?
(c) Le graphe P est-il Eulérien ?
(d) Déterminer le nombre minimum de couleurs nécessaires pour avoir un coloriage propre des
sommets de P .
(e) L’excentricité d’un sommet u est défini comme ϵ(v) = maxu∈V d(v, u). Le rayon du graphe est
défini comme minv∈V ϵ(v). Que vaut le rayon de P ?
(f) Donner la matrice d’adjacence de P . Vérifier (un argument simple suffit) que 3 en est une valeur
propre.
(Août 2015, question 2)

20
Théorie des graphes 2022 – 2023

Exercice 4.5. Soit le graphe de Pappus G représenté ci-dessous.

(a) Ce graphe est-il hamiltonien ?

(b) Ce graphe est-il eulérien ?
(c) Montrer que G est un graphe 2-colorable. En déduire que G est biparti.
(d) Montrer, sans calcul, que 3 est valeur propre et que 4 n’est pas valeur propre de G.
(Janvier 2016, question 2)
Exercice 4.6. Soit le graphe de Turan G représenté ci-dessous.

(a) Ce graphe est-il hamiltonien ?

(b) Ce graphe est-il eulérien ?
(c) Ce graphe est-il planaire ?
(d) Fournir la matrice d’adjacence de ce graphe. √ √
(e) Sachant que les valeurs propres sont −1, 0, 2 + 14, 2 − 14, peut-on en déduire que ce graphe
est biparti ?
(f) Expliquer pourquoi il n’existe aucun coloriage propre des sommets du graphe avec moins de 6
couleurs. Donner un coloriage propre de G avec 6 couleurs.
(g) La matrice d’adjacence est-elle primitive ?
(Août 2016, question 5)
Exercice 4.7. Soit le graphe G à 12 sommets représenté ci-dessous.

(a) Ce graphe est-il hamiltonien ? Quelle est sa fermeture ?

(b) Ce graphe est-il eulérien ?
(c) Montrer que G est un graphe 4-colorable qui n’est pas 3-colorable.
(d) Ajouter au plus 3 arêtes au graphe pour qu’il ne soit plus planaire.
(e) Représenter le dual de cette représentation planaire de G. Quel est le nombre minimum de cou-
leurs à utiliser pour colorer les faces de cette représentation planaire de G, des faces adjacentes
recevant des couleurs distinctes ?
(Janvier 2017, question 2)

21
Théorie des graphes 2022 – 2023

Exercice 4.8. Soit le graphe G à 15 sommets représenté ci-dessous.

(a) Ce graphe est-il hamiltonien ? Quelle est sa fermeture ?

(b) Ce graphe est-il eulérien ? S’il ne l’est pas, ajouter au plus 3 arêtes pour le rendre eulérien.
(c) Montrer que G est un graphe 3-colorable (pour les sommets) qui n’est pas 2-colorable.
(d) Ce graphe est-il biparti ?
(e) Représenter le dual de cette représentation planaire de G. Quel est le nombre minimum de cou-
leurs à utiliser pour colorer les faces de cette représentation planaire de G, des faces adjacentes
recevant des couleurs distinctes ?
(Août 2017, question 2)

22
 Examen écrit de théorie des graphes
Janvier 2018

Consignes : Il est attendu que les réponses fournies soient clairement justifiées. La
clarté, la rédaction et la justification des réponses fournies interviennent dans la
cotation.
Bon travail !

Théorie (uniquement pour les étudiants ayant passé le projet)

(1) Démontrer que le graphe complet K5 n’est pas planaire.
(2) Définir les notions de graphe biparti, de tri topologique d’un graphe orienté,
d’homomorphisme de graphes, de matrice primitive.
(3) Appliquer l’algorithme de Dijkstra au graphe orienté et pondéré suivant,
source s. On considérera les itérations successives de l’algorithme en four-
nissant les valeurs des variables T (v) et C(v) pour chaque sommet v 6= s
(poids actuel et chemin réalisé pour le sommet v)
a
4
s
4
1
5 b 2 c

9 2
8
d f
3 e 1

Exercices (pour tous)

(1) (5 points) Soit G un graphe simple. Le graphe ligne de G, noté L(G), est
construit comme suit : à chaque arête de G correspond un sommet de L(G).
Deux arêtes de G sont adjacentes (i.e., ont une extrémité en commun) si et
seulement si les sommets correspondants de L(G) sont voisins.
(a) Tracer le graphe ligne associé au graphe suivant :

(b) Montrer que si G est eulérien, alors L(G) est hamiltonien.

(c) Soit {u, v} une arête de G. A cette arête, correspond un sommet de
L(G). Comment exprimer le degré de ce sommet de L(G) à partir des
degrés de u et v dans G ?
(d) Montrer que si G est eulérien, alors L(G) est eulérien.
(e) Donner un exemple de graphe G qui n’est ni hamiltonien, ni eulérien
et pour lequel L(G) est hamiltonien.
2

(2) (5 points) On considère les 4 graphes ci-dessous.

F G

H I

(a) Parmi ces graphes, lesquels sont eulériens ? Justifier.

(b) Parmi ces graphes, lesquels sont hamiltoniens ? Justifier.
(c) Pour chaque graphe, combien de couleurs sont nécessaires pour avoir
un coloriage propre des sommets ?
(d) Retirer un nombre minimum d’arêtes à H pour en faire un arbre.
(3) (5 points) On considère le graphe de Dürer représenté ci-dessous

(a) Donner la matrice d’adjacence M de ce graphe.

(b) Prouver que cette matrice M est primitive (Suggestion : il n’est pas
nécessaire d’en calculer explicitement des puissances).
(c) Sans faire le calcul, pourquoi les éléments diagonaux de M 2 sont-ils
tous égaux à 3 ?
(d) Même question avec M 3 , pourquoi ses éléments diagonaux sont-ils
égaux soit à 2, soit à 0 ?
(e) Sachant que le diamètre du graphe vaut 4 (i.e., la distance entre deux
sommets quelconques est au plus 4 et il existe deux sommets dont la
distance est exactement 4), quel renseignement pouvez-vous tirer sur les
puissances de M ?

(4) (5 points) On considère un graphe planaire connexe G ayant 80 faces trian-

gulaires et 12 faces pentagonales. De chaque sommet de G partent quatre
faces triangulaires et une face pentagonale. Déterminer le nombre de som-
mets et le nombre d’arêtes de G. Justifier votre raisonnement.
 Examen écrit de théorie des graphes
Août 2018

Consignes : Il est attendu que les réponses fournies soient clairement justifiées. La
clarté, la rédaction et la justification des réponses fournies interviennent dans la
cotation.
Bon travail !

Théorie (uniquement pour les étudiants ayant passé le projet)

(1) Décrire l’algorithme du PageRank :
a) Quel est le modèle de graphe retenu ?
b) Définir le PageRank d’une page.
c) Quelles sont les matrices construites, jusqu’à l’obtention de la "matrice
de Google" ? Quelles sont leurs éventuelles propriétés ?
d) Comment est réalisé le calcul des PageRanks et sur quels résultats ma-
thématiques se base-t-il ?
(2) Définir les notions et, à chaque fois, donner un exemple de
a) graphe biparti,
b) tri topologique d’un graphe orienté,
c) graphe eulérien,
d) graphe planaire.

Exercices (pour tous)

(1) (5 points)
a) Soit G un graphe simple connexe et non-orienté. Prouver que si G
contient exactement un sommet de degré 1, alors G contient un piste
fermée (on n’utilise pas deux fois la même arête).
b) Prouver qu’un graphe H simple et non-orienté est une forêt (union dis-
jointe d’arbres) si et seulement si tout sous-graphe induit de H contient
un sommet de degré au plus 1.
(2) (5 points) Appliquer l’algorithme de Dijkstra au graphe orienté et pondéré
suivant, de source s. On considérera les itérations successives de l’algorithme
en fournissant les valeurs des variables T (v) et C(v) pour chaque sommet
v 6= s (poids actuel et chemin réalisé pour le sommet v)
a
4
s
4
1
5 b 2 c

9 2
8
d f
3 e 1
2

(3) (5 points) On considère le graphe de Frucht représenté ci-dessous.

(a) Donner la matrice d’adjacence M de ce graphe.

(b) Prouver que cette matrice M est primitive. (Suggestion : il n’est pas
nécessaire d’en calculer explicitement des puissances.)
(c) Sans faire le calcul, pourquoi les éléments diagonaux de M 2 sont-ils
tous égaux à 3 ?
(d) Même question avec M 3 , pourquoi ses éléments diagonaux sont-ils
égaux soit à 2, soit à 0 ? On précisera lesquels sont nuls.
(e) Prouver que ce graphe est hamiltonien.
(f) Est-il eulérien ?

(4) (5 points) On considère un graphe planaire connexe G ayant 32 faces tri-

angulaires et 6 faces carrées. De chaque sommet de G partent quatre faces
triangulaires et une face carrée. Déterminer le nombre de sommets et le
nombre d’arêtes de G. Justifier votre raisonnement.
 Examen de théorie des graphes — Janvier 2019

Consignes : Il est attendu que les réponses fournies soient clairement justifiées. La
clarté, la rédaction et la justification des réponses fournies interviennent dans la
cotation. Feuilles distinctes pour théorie et exercices !

• Pour les étudiants n’ayant PAS présenté le projet.

Th. 1 Enoncer et démontrer le théorème de Dirac.

Th. 2 Donner un exemple de graphe non orienté possédant au moins deux cycles
dont la matrice d’adjacence est irréductible, mais pas primitive. Pour cet
exemple, quelle en est la période ?
Th. 3 Enoncer une caractérisation algébrique des graphes bipartis.
Th. 4 Définir les nombres de Ramsey. Expliquer pourquoi R(3, 3) > 5 ?
Comment généraliser les nombres de Ramsey à plus de 2 couleurs ?

• Pour les étudiants ayant présenté le projet.

Th. 1 Définir la notion de graphe hamiltonien. Donner un exemple de graphe

hamiltonien et un exemple de graphe non hamiltonien. Ces graphes auront
au moins 6 sommets.
Th. 2 Fournir tous les tris topologiques du graphe ci-dessous (il y en a 7) :
a d
f
c
b e

Th. 3 a) Définir la notion de matrice primitive.

b) La matrice suivante est-elle primitive ? (plusieurs justifications sont pos-
sibles)  
1 1 0
M = 0 0 1 .
1 1 0
c) Sachant que ses valeurs propres sont
1 √  1 √ 
1 + 5 ≃ 1, 618; 1 − 5 ≃ −0, 618; 0
2 2
quels renseignements tirez-vous sur M n quand n → ∞ ?
d) Représenter le graphe orienté ayant M pour matrice d’adjacence.
Th. 4 Donner les parcours préfixe, infixe et suffixe de l’arbre ci-dessous
a

b c

d e

f g

h i
2

• • Pour TOUS les étudiants — partie exercices

Ex. 1 On considère l’algorithme suivant auquel on fournit en entrée un graphe

simple non orienté G = (V, E). Pour rappel, ν(u) dénote l’ensemble des voi-
sins de u.
Considérer un sommet quelconque v0 ∈ V
Composante:= {v0 }, New:= {v0 }, Aretes:= ∅
Tant que New6= ∅
Voisins:= ∅
pour tout sommet u appartenant à New
Voisins:= Voisins ∪ ν(u)
New:= Voisins\Composante
pour tout sommet v appartenant à New
sélectionner une arête {v, w} telle que w ∈Composante
ajouter cette {v, w} à Aretes
Composante:= Composante ∪ New
v0
a) Appliquer l’algorithme au graphe ci-contre.
b) Après l’exécution de cet algorithme, que
contient Composante ? Justifier.
c) quelles propriétés possède le graphe
(Composante,Aretes) obtenu ? Justifier.
d) Dans quelle situation « réelle » pourrait-on
utiliser cet algorithme ?

Ex. 2 On donne le graphe orienté ci-dessous

1 2

5 4
3
a) Donner sa matrice d’adjacence A.
b) Donner les éléments de la diagonale de A3 . Justifier.
c) Quel est le nombre minimum d’arc(s) à ajouter pour rendre le graphe
fortement connexe ? Fournir ce(s) arc(s).
d) Donner un chemin simple de longueur maximale. Justifier.
e) Avec les notations du cours, si ce graphe est vu comme un ensemble de
pages Web et de liens, donner les matrices H (hyperliens) et S (stochas-
tique) utilisées dans l’algorithme du PageRank. Comment calculerait-on
la matrice G utilisée par Google (une formule détaillée suffit).

Ex. 3 On considère un graphe planaire connexe G ayant 8 faces triangulaires et

18 faces carrées. De chaque sommet de G partent trois faces carrées et une
face triangulaire. Déterminer le nombre de sommets et le nombre d’arêtes de
G. Justifier votre raisonnement.

Ex. 4 a) Prouver que dans un graphe simple connexe (non orienté) deux chemins
simples de longueur maximale ont toujours un sommet commun.
b) Prouver que si un graphe possède exactement deux sommets de degré
impair, alors ces sommets sont connectés par un chemin.
 Examen de théorie des graphes — Août 2019

Consignes : Il est attendu que les réponses fournies soient clairement justifiées. La
clarté, la rédaction et la justification des réponses fournies interviennent dans la
cotation. Feuilles distinctes pour théorie et exercices !

• Pour les étudiants n’ayant PAS présenté le projet.

Th. 1 Enoncer et démontrer une caractérisation algébrique des graphes bipartis.

Th. 2 Donner un exemple de graphe non orienté possédant au moins deux cycles
dont la matrice d’adjacence est irréductible, mais pas primitive. Pour cet
exemple, quelle en est la période ?
Th. 3 Enoncer le théorème de Dirac.

• Pour les étudiants ayant présenté le projet.

Th. 1 Fournir tous les tris topologiques du graphe suivant.

b d f

c e g
Th. 2 Pourquoi peut-on affirmer que le graphe suivant est primitif ?

Sachant que les valeurs propres de la matrice d’adjacence M du graphe sont

λ1 ≃ 1.8, λ2 ≃ −1.25 et λ3 ≃ 0.44, quel renseignement peut-on tirer sur M n
si n → +∞.
Th. 3 Pour des graphes ayant au moins 8 sommets, donner un exemple de graphe
planaire et un exemple de graphe non planaire (justifier vos choix).
Th. 4 Donner les parcours préfixe, infixe et suffixe de l’arbre ci-dessous
a

b c

d e

f g

h i
2

• • Pour TOUS les étudiants — partie exercices

Ex. 1 Au Sudoku 4 × 4, le but du jeu est de remplir les cases avec des chiffres
allant de 1 à 4 en veillant toujours à ce qu’un même chiffre ne figure qu’une
seule fois par colonne, une seule fois par ligne, et une seule fois par carré de
quatre cases (la grille étant composée de 4 tels carrés disjoints). Par exemple,
une grille valide est donnée par
1 3 2 4
4 2 3 1
3 4 1 2
2 1 4 3
a) Modéliser le Sudoku 4 × 4 par un graphe à 16 sommets de telle sorte
que les grilles valides correspondent exactement aux coloriages valides de
ce graphe avec 4 couleurs (des sommets voisins reçoivent des couleurs
distinctes). Combien ce graphe possède-t-il d’arêtes ?
b) Le graphe obtenu est-il eulérien ? Justifier.
c) Montrer qu’il est hamiltonien en fournissant un circuit convenable.
d) Existe-t-il une valeur de k telle qu’il soit k-régulier ? En fonction de votre
réponse, que pouvez-vous dire de la valeur propre de plus grand module
(de la matrice d’adjacence) ?

Ex. 2 On donne le graphe orienté ci-dessous

a) Donner sa matrice d’adjacence A.

b) Quel est le plus petit entier n > 0 tel que tous les éléments de la diagonale
de An sont > 0 ? Que trouve-t-on sur cette diagonale ? Justifier.
c) Quelles sont les composantes fortement connexes du graphe ?
d) Quel est le nombre minimum d’arc(s) à ajouter pour rendre le graphe
fortement connexe ? Fournir ce(s) arc(s).
e) Donner un chemin hamiltonien pour ce graphe (bonus : donner tous les
chemins hamiltoniens).

Ex. 3 Soit un graphe planaire connexe possédant uniquement des faces triangu-
laires et carrées. Chaque sommet appartient exactement à une face carrée et
4 faces triangulaires. Déterminer le nombre de sommets, d’arêtes et de faces
de ce graphe. Justifier votre raisonnement.

Ex. 4 Dans une forêt formée de k ≥ 1 arbres disjoints, quelle relation existe-t-il
entre le nombre total de sommets et d’arêtes ? Justifier votre réponse.
 Examen de théorie des graphes — Janvier 2020

Consignes : Il est attendu que les réponses fournies soient clairement justifiées. La
clarté, la rédaction et la justification des réponses fournies interviennent dans la
cotation. Feuilles distinctes pour théorie et exercices !

• Pour les étudiants n’ayant PAS présenté le projet.

Th. 1 Répondez à une des deux questions ci-dessous, AU CHOIX

1.1 Enoncer et démontrer une caractérisation (condition nécessaire et suffi-
sante) des graphes bipartis connexes par leur spectre.
1.2 Définir les nombres de Ramsey et prouver qu’ils existent.
Th. 2 Donner un exemple de graphe orienté possédant au moins deux automor-
phismes non triviaux distincts (donnez ces automorphismes).
Th. 3 Que peut-on dire du comportement asymptotique de An quand A est une
matrice primitive ? Précisez le contexte et les notations utilisées.
Th. 4 Qu’est que la fermeture d’un graphe ? Donner deux graphes à 6 sommets
(ditincts de K6 ) dont la fermeture est/n’est pas K6 .
Th. 5 Donnez un exemple de graphe simple orienté fortement connexe dont la
période vaut 3 et qui contient au moins 8 sommets. Expliquez votre construc-
tion.
Th. 6 Soit G un graphe orienté possédant n sommets et ℓ arcs. On définit un
graphe H obtenu à partir de trois copies distinctes de G, notées G1 , G2 et G3 .
Ainsi H a 3n sommets. Pour définir H, on y ajoute encore, un arc joignant
chaque sommet de Gi à chaque sommet de Gj si et seulement si i < j.
a) Combien H possède-t-il d’arcs (en fonction de n et ℓ) ?
b) Connaissant le spectre de G, que savez-vous du spectre du H ?

• Pour les étudiants ayant présenté le projet.

Th. 1 Définir la notion de tri topologique. Décrivez une méthode (ou un algo-
rithme) permettant d’obtenir un tel tri. Appliquez-là à un graphe de votre
choix ayant 5 sommets.
Th. 2 Donnez une condition nécessaire et suffisante pour qu’un graphe orienté
soit eulérien.
Th. 3 Justifier que dans un graphe simple connexe G = (V, E), on a toujours
#E ≥ #V − 1.
Th. 4 Donnez un exemple de graphe simple orienté fortement connexe dont la
période vaut 3 et qui contient au moins 8 sommets. Expliquez votre construc-
tion.
Th. 5 On admettra que, dans un graphe à n ≥ 2 sommets, s’il existe un chemin
entre deux sommets alors il existe un chemin de longueur au plus n − 1 (ce
résultat est donc supposé connu).
A partir de la matrice d’adjacence A d’un graphe orienté, comment détec-
ter si un graphe est ou non fortement connexe ? Quels « calculs » allez-vous
réaliser ? Justifier votre démarche.
2

• • Pour TOUS les étudiants — partie exercices

Ex. 1 On considère le graphe suivant (appelé graphe de Herschel).

a) Ce graphe est-il eulérien ? (Justifier votre réponse)

b) Est-il hamiltonien ? Possède-t-il un chemin hamiltonien ? (Si oui, fournir
un circuit/chemin hamiltonien ; si non, justifier.)
c) Est-il biparti ? Si oui, fournir une partition convenable de l’ensemble des
sommets.
d) Peut-on lui appliquer la formule d’Euler ? Si oui, le faire.
e) Quel est le nombre minimum de couleurs nécessaires pour colorier les
arêtes de ce graphe de telle sorte que des arêtes adjacentes reçoivent des
couleurs distinctes.
Bonus) Ce graphe est-il le squelette d’un polyèdre convexe ?

Ex. 2 Si A est une matrice à coefficients naturels, on définit la matrice T (A) de

même dimension et à coefficients dans {0, 1}, de sorte que [T (A)]i,j = 1 si et
seulement si Ai,j > 0. Par exemple,
   
3 1 1 1
si A = , alors, T (A) = .
0 2 0 1
 
0 1 1 0 0 0 1
 1 0 1 0 0 0 0 
 
 1 1 0 1 0 0 0 
 
Soit la matrice symétrique M =   0 0 1 0 1 0 0 .

 0 0 0 1 0 1 0 
 
 0 0 0 0 1 0 1 
1 0 0 0 0 1 0
a) Représenter les trois graphes non orientés ayant respectivement M, T (M 2 )
et T (M + M 2 ) comme matrice d’adjacence.
b) Sans effectuer le calcul de M 6 , que vaut T (M 6 ) ? Justifier.
c) Soit k ≥ 1. D’une manière générale, si T (A + A2 + · · · + Ak ) contient un
élément nul et si T (A + A2 + · · · + Ak + Ak+1 ) a tous ses éléments égaux
à 1, quel(s) renseignement(s) tire-t-on sur le graphe associé à A ?

Ex. 3 On considère un graphe planaire, connexe et 3-régulier (chaque sommet

est de degré 3). Toutes les faces de ce graphe sont des carrés, des hexagones ou
des octogones. Chaque sommet appartient à la frontière d’une face de chacun
des trois types. Déterminer le nombre de sommets, d’arêtes et de faces de
chaque type.

Ex. 4 a) Démontrer qu’un arbre ayant au moins 3 sommets possède au moins

deux feuilles, i.e., deux sommets de degré 1.
b) Soit G = (V, E) un graphe connexe (non orienté) ayant au moins 3 som-
mets. Démontrer qu’il existe deux sommets u, v ∈ V tels que les trois
graphes G − u, G − v, G − {u, v} soient connexes.
 Examen d’algèbre vendredi 15 janvier 2021
bacheliers en sc. mathématiques et informatiques

Consignes : Répondre à la théorie et aux exercices sur des feuilles distinctes.

La clarté, la rédaction et la justification des réponses fournies intervien-
nent dans la cotation. Enoncer les résultats utilisés. Fin de l’examen
15h30. Bon travail.

› Pour les étudiants ne présentant pas le projet

1. Donner un exemple de graphe orienté à 4 sommets ne con-

tenant pas de boucle (cycle de longueur 1) et dont la matrice
d’adjacence est primitive — argumenter votre construction.

Un circuit de 4 sommets 1 ! 2 ! 3 ! 4 ! 1 plus un

arc 2 ! 4 suffit. En effet, le graphe est fortement connexe
donc sa matrice est irréductible. De plus, sa période vaut 1
puisqu’on trouve (partant du sommet 1) un cycle de longueur
4 et un cycle de longueur 3. Donc le pgcd des longueurs vaut
1. On conclut en se rappelant qu’une matrice irréductible
et apériodique (i.e., période 1) est primitive. Une alternative
est de calculer une puissance suffisante (10) de la matrice
d’adjacence.

2. Énoncer et démontrer le théorème de Dirac.

3. Justifier l’inégalité R(3; 3) > 5 (concernant les nombres de

Ramsey).

Il faut exhiber un coloriage des arêtes d’un graphe com-

plet à 3 (resp. 4, 5) sommets ne contenant aucun trian-
gle monochromatique. Rappeler la définition du nombre de
Ramsey R(s; t).

› Pour les étudiants ayant présenté le projet

1. Construire un graphe simple orienté dont les 7 sommets sont

a; b; c; d; e; f; g, ayant 10 arcs et possédant au moins les 3 tris
topologiques
a<b<c<d<e<f <g ;
a < c < b < d < e < g < f et
b < a < c < d < e < g < f.
Un graphe répondant à la question est donné par :

a f
b d e
c g

Dans un tri topologique, s’il y a un arc ¸ ! ˛ alors, ¸ sera

énuméré avant ˛. Ne pas oublier de mettre 10 arcs.
 2. Recopier l’arbre sur votre feuille (à trois reprises)

y placer les labels des sommets de telle sorte que l’énumération

1; 2; 3; : : : ; 10; 11 soit préfixe, infixe puis suffixe. Si un som-
met possède un seul fils, on suppose qu’il s’agit du fils de
gauche.
1 11 11

2 4 10

3 6 3 8 3 9

4 7 10 2 6 10 2 6 8

5 8 9 11 1 5 7 9 1 4 5 7

3. Donner un exemple de graphe à 8 sommets hamiltonien mais

non eulérien (justifier).

Un cycle à 8 sommets auquel on ajoute une arête entre deux

sommets non adjacents suffit. En effet, ces deux sommets
sont alors de degré 3 (impair). Or un graphe est eulérien si et
seulement si tous les sommets sont de degré pair. Puisqu’on
a un cycle passant par les 8 sommets, le graphe est bien
hamiltonien (circuit passant une et une seule fois par chaque
sommet).

› Pour TOUS (exercices 20 points)

1. (5 points) On considère le graphe H formé de deux copies du

graphe biparti complet K3;3 auxquelles on ajoute une arête
entre les sommets correspondants des deux copies (on ajoute
ainsi 6 arêtes).

a) Combien le graphe H possède-t-il d’arêtes ?

Chaque copie de K3;3 possède 3 ˆ 3 = 9 arêtes. On a
donc 9 + 9 + 6 = 24 arêtes dans H.
 b) Ce graphe est-il eulérien ? Justifier.
Dans K3;3 chaque sommet est de degré 3, mais avec
l’arête joignant les sommets correspondants des deux
copies, chaque sommet de H est de degré 4. Ainsi, H est
un graphe connexe dont tous les sommets sont de degré
pair. C’est une caractérisation des graphes eulériens.
c) Est-il hamiltonien ? Si oui, donner un circuit hamil-
tonien.
Si une copie de K3;3 a pour sommets 1; : : : ; 6 et pour
arêtes fi; jg avec 1 » i » 3 et 4 » j » 6, on note
les sommets correspondants dans la deuxième copie par
10 ; : : : ; 60 . On a par exemple le circuit hamiltonien,
1 ` 4 ` 2 ` 5 ` 3 ` 6 ` 60 ` 30 ` 50 ` 20 ` 40 ` 10 ` 1:

d) Expliquer pourquoi 2 couleurs suffisent pour obtenir un

coloriage propre des sommets de H.
Avec les notations du point précédent, 1; 2; 3; 40 ; 50 ; 60
peuvent recevoir une même couleur. Par définition de
H, ces 6 sommets sont indépendants (pas d’arête entre
eux). Il en va de même des sommets 4; 5; 6; 10 ; 20 ; 30 .
e) Peut-on obtenir une représentation planaire du graphe ?
Si oui, en fournir une. Si non, justifier.
Au vu du thm. de Kuratowski, puisque H contient K3;3
comme sous-graphe, H ne peut pas être planaire. Alter-
native, il n’est même pas nécessaire de faire référence
à Kuratowski : un graphe contenant un graphe non
planaire comme sous-graphe ne peut être planaire.
2. (7 points) On considère un graphe non orienté formé d’un
cycle de 5 sommets numérotés de 1 à 5 ainsi qu’une arête
supplémentaire joignant les sommets 1 et 3.
a) Donner la matrice d’adjacence M du graphe.
0 1
B
0 1 1 0 1 C
B
B
B
1 0 1 0 0 C
C
C
M = B
B
B
1 1 0 1 0 C
C
C
B
B
@
0 0 1 0 1 C
C
A
1 0 0 1 0

b) Montrer qu’il y a 15 circuits de longueur 4 partant et

arrivant dans le sommet 1.
Sans être élégant, on peut calculer la puissance 4ième
de la matrice d’adjacence
0 1
B
15 8 7 11 3 C
B
B
B
8 8 8 6 6 C
C
C
B
B
B
7 8 15 3 11 C
C
C
B
B
@
11 6 3 9 1 C
C
A
3 6 11 1 9
 et l’élément dans le coin supérieur gauche compte le
nombre de tels circuits (chemins de longueur 4 partant
et revenant en 1).
c) Vérifier que le vecteur de composantes
v = (`1; 0; 1; `1; 1) est un vecteur propre de M. En
déduire une valeur propre.
On vérfiera (calculs à faire) que M:v = (`2)v donc `2
est valeur propre.
d) La matrice est-elle irréductible ? Primitive ?
Le graphe est fortement connexe et possède un circuit de
longueur 3 et un circuit de longueur 5, ainsi, sa période
vaut 1. Un graphe irréductible et apériodique est primitif.
Si on a calculé la puissance 4ième de M au point b), une
alternative est de voir que les éléments de cette matrice
sont tous > 0.
e) Si on considère cette fois, un cycle de 6 sommets et
une arête supplémentaire joignant les sommets 1 et 4,
la matrice d’adjacence est-elle primitive ? Quelle est la
période du graphe et de là, quels renseignements pouvez-
vous obtenir sur l’existence de chemins de longueur n
joignant les sommets 1 et 3 ?
Contrairement au point précédent, même si le graphe
reste connexe (la matrice est donc irréductible), les cy-
cles que l’on peut trouver sont de longueur 4, 6, 8, etc.
Ainsi, le pgcd des longueur de cycles vaut 2. (On a aussi,
dans le cas non orienté, des cycles du type 1 ` 2 ` 1
de longueur 2.) La période de ce graphe vaut 2, la
matrice n’est pas primitive. Si un chemin existe entre
les sommets 1 et 3, il est nécessairement de longueur
paire. Plus précisément, les longueurs pour lesquelles
on trouve au moins un tel chemin sont 2, 4 (avec, par
exemple, 1 ` 2 ` 3 ` 2 ` 3), 6, 8, 10, 12, etc. On
met donc en évidence le thm. de structure vu au cours.
On a un chemin de longueur 2n pour tout n – 1. On
utilise autant que nécessaire des cycles de longueur 4 ou
6 du sommet 1 vers lui-même pour finir avec un chemin
1 ` 2 ` 3.
3. (5 points) On considère un graphe planaire connexe G ayant
20 faces triangulaires et p faces pentagonales (où p > 0).
De chaque sommet de G partent exactement 2 faces trian-
gulaires et 2 faces pentagonales. Déterminer le nombre de
sommets, d’arêtes et de faces pentagonales de G.
On désigne par s; a; f respectivement le nombre de sommets,
d’arêtes et de faces du graphe. Nous pouvons utiliser la
formule d’Euler (graphe planaire et connexe),

s ` a + f = 2:

On note p le nombre de faces pentagonales. On a les rela-

tions suivantes (certaines sont redondantes) :

f = 20+p; 4s = 2a; 5p+3:20 = 2a; 2s = 5p; 2s = 3:20:

La deuxième relation provient du fait que chaque sommet est

de degré 4 (4 arêtes partent de chaque sommet mais chaque
arête a 2 extrémités). La troisième relation exprime que les
faces sont délimitées par 5 ou 3 arêtes et que chaque arête
appartient à la frontière de 2 faces. La relation suivante ex-
prime que chaque sommet appartient à la frontière de deux
faces pentagonales (et chaque face pentagonale a, dans sa
frontière, 5 sommets). Enfin, la dernière relation exprime
que chaque sommet appartient à la frontière de 2 faces tri-
angulaires (et chaque face triangulaire a, dans sa frontière, 3
sommets). Ce système d’équations linéaires a pour solution
unique

s = 30; p = 12; a = 60; f = 32:

4. (3 points) On dispose de 9 émetteurs localisés géographique-

ment comme ci-dessous. Sur la figure, on a aussi représenté
le rayon d’action spécifique de ceux-ci. On veut éviter les in-
terférences : 2 émetteurs ayant une zone d’action commune
doivent émettre sur des fréquences différentes.
Minimiser le nombre de fréquences différentes à allouer pour
éviter les interférences.
 7

9
8
2 6
1

5
3 4

Modéliser ce problème en un problème de théorie des graphes

: préciser votre choix de sommets et d’arêtes. Quelle notion
est importante ? Ensuite, représenter le graphe correspon-
dant et résoudre le problème ainsi traduit.
On considère un graphe à 9 sommets. Chaque sommet corre-
spond à un émetteur. Une arête connecte deux sommets si et
seulement si l’intersection des zones d’action des émetteurs
correspondants est non vide.

9
8
2 6
1

5
3 4

Il s’agit d’un problème de coloriage propre. On a deux copies

de K4 (f1; 2; 3; 8g et f4; 5; 6; 8g), il faut donc au minimum 4
couleurs. En fait, 4 couleurs suffisent: f1; 4g, f2; 5; 7g, f3; 6g
et f8; 9g sont 4 sous-ensembles de sommets indépendants. Il
ne s’agit pas du seul coloriage possible. On assigne la même
fréquence à tous les émetteurs recevant la même couleur.
 Examen de théorie des graphes 21 janvier 2022
bacheliers en sc. mathématiques et informatiques

Consignes : Répondre à la théorie et aux exercices sur des

feuilles distinctes. La clarté, la rédaction et la justification des
réponses fournies interviennent dans la cotation. Enoncer les
résultats utilisés. Lorsqu’une question contient plusieurs points,
pour répondre à une partie, on admettra les points précédents.
Fin de l’examen 17h30. Bon travail.

› Pour les étudiants ne présentant pas le projet

1. Définir les notions de parcours préfixe et suffixe

d’un arbre. Donner un exemple montrant que ces
deux parcours sont différents.
2. Enoncer et démontrer le résultat caractérisant un
graphe biparti par son spectre (condition néces-
saire et suffisante).
3. Donner un exemple de graphe planaire montrant
qu’il faut au moins 4 couleurs pour avoir un colo-
riage propre de ses faces.

› Pour les étudiants ayant présenté le projet

1. Recopier l’arbre sur votre feuille (à trois reprises)

y placer les labels des sommets de telle sorte que

l’énumération 1; 2; 3; : : : ; 10; 11 soit préfixe, infixe
puis suffixe. Si un sommet possède un seul fils,
on suppose qu’il s’agit du fils de gauche.
2. Détailler les grandes étapes d’un algorithme (en
français ou pseudo-code) permettant de tester si
un multi-graphe non orienté est ou non eulérien.
› Pour TOUS (exercices 20 points)

1. (6 points) On considère le graphe G non orienté

représenté ci-dessous.

2
4 5

1 3

a) Ce graphe est-il eulérien ? Est-il hamiltonien ?

Justifier. En cas de réponse positive, fournir
un circuit convenable.
b) Donner un coloriage propre des sommets du
graphe utilisant un nombre minimum de couleurs.
c) Ce graphe est-il biparti ? Justifier.
d) Donner la matrice d’adjacence du graphe (pour
la numérotation des sommets proposée).
e) Cette matrice est-elle primitive ? On peut
justifier sans en calculer des puissances.
f) Combien y-a-t-il de circuits de longueur 3 dé-
marrant et aboutissant dans le sommet 1 ?
Même question avec le sommet 6.

2. (5 points) On considère un graphe planaire con-

nexe G dont toutes les faces sont carrées, hexago-
nales ou décagonales (4; 6; 10 côtés). De chaque
sommet partent une face de chacun des trois types.
On note s le nombre de sommets, a le nombre
d’arêtes et c; h; d le nombre de faces des différents
types.
a) Exprimer la formule d’Euler liant s; a; c; h; d.
b) Quelle relation liant s et c déduisez-vous des
données ?
c) Quelle relation liant s et h pouvez-vous tirer ?
 d) Quelle relation liant s et d pouvez-vous tirer ?
e) Quelle relation liant a et c; h; d pouvez-vous
tirer ?

Enfin, déterminer les valeurs de s; a; c; h; d.

(Suggestion : pour vérifier vos calculs, vous de-
vez trouver un nombre total de faces de 62 —
vous ne pouvez pas utiliser cette information telle
quelle dans votre résolution.).

3. (5 points) Soit G = (V; E) un graphe simple non

orienté. Pour tout sommet v, on définit la fonc-
tion f : V ! Q comme la moyenne arithmétique
des degrés des voisins de v, c’est-à-dire
1 X
f(v) = deg(x):
#(v) x2(v)

Pour rappel, (v) désigne l’ensemble des voisins

de v. Si v est un sommet isolé, alors f(v) = 0.
Un exemple est donné ci-dessous :

10/ 3

4 10/ 4 10/ 3

10/ 3

a) Si A est la matrice d’adjacence de G et si e

désigne un vecteur colonne ne contenant que
des 1, exprimer f(v) à l’aide des composantes
de A e et A2 e.
b) Si G est le graphe complet Kn . Montrer que
f(v) est constant et déterminer cette con-
stante.
c) Faire de même si G est un graphe k-régulier
(k – 2). En quoi votre réponse est-elle co-
hérente avec le point précédent ?
d) Si G est le graphe biparti complet Km;n ,
m – n – 1, quelle(s) valeur(s) peut prendre
f(v) ?
 e) Soit r le degré maximal des sommets de G.
Montrer que f(v) » r pour tout sommet v.
Donner une condition suffisante pour que la
valeur maximale r puisse être atteinte ? Don-
ner un exemple où elle est atteinte et un où
elle ne l’est pas.

4. (4 points) Soit G un graphe simple orienté sans

cycle possédant un chemin hamiltonien.

a) Donner un exemple d’un tel graphe avec 6

sommets et 9 arcs.
b) Justifier que ce chemin hamiltonien permet
de définir un tri topologique des sommets
c) Montrer que G possède un unique sommet u
de demi-degré entrant nul.
d) Montrer que G ` u possède encore un chemin
hamiltonien.
e) Déduire des deux points précédents que G
possède un unique tri topologique.