(2026) Des graphes aux groupes... et vice-versa

Exposé pour un atelier lors des journées nationales de l'APMEP 2026 à Strasbourg. Il s'agit essentiellement de présenter la preuve originelle du théorème de Frucht (1939) sur les groupes d'automorphismes d'un graphe.

Transcript

1. Des graphes aux groupes... et vice-versa Roger Mansuy Journées APMEP, Strasbourg 2026
2. Définition. Un graphe non orienté est un couple (S, A) avec • S une partie finie • A une partie de P2 (S). Les éléments de S sont appelés sommets et ceux de A arêtes.
3. On appréhende souvent un graphe par un dessin: des points du plan pour les sommets et des segments (ou des arcs pour les arêtes). Par exemple, le graphe de sommets 1, 2 et 3, et d’arêtes {1, 2}, {1, 3} et {2, 3} est appelé triangle et dessiné comme 2 1 3
4. On appréhende souvent un graphe par un dessin: des points du plan pour les sommets et des segments (ou des arcs pour les arêtes). Par exemple, le graphe de sommets 1, 2 et 3, et d’arêtes {1, 2}, {1, 3} et {2, 3} est appelé triangle et dessiné comme 3 2 1 3 1 2
5. On appréhende souvent un graphe par un dessin: des points du plan pour les sommets et des segments (ou des arcs pour les arêtes). Par exemple, le graphe de sommets 1, 2 et 3, et d’arêtes {1, 2}, {1, 3} et {2, 3} est appelé triangle et dessiné comme 3 2 1 3 1 2 2 1 3
6. Définition. Soit G = (S, A) un graphe. . Le degré d’un sommet x ∈ S est le nombre d’arêtes issues de x, c’est-à-dire {y ∈ S, {x, y} ∈ A} . . Un chemin de longueur k entre deux sommets x et y est une suite de sommets x0 , x1 , …, xk ∈ S tels que x0 = x, xk = y et ∀k ∈ J1, kK, {xk−1 , xk } ∈ A. . La distance entre deux sommets x et y est, quand elle existe, la plus petite longueur d’un chemin entre x et y.
7. Des graphes aux groupes Dans cette section, on part d’un graphe et on lui associe un groupe.
8. Pour comprendre un graphe, on cherche à en déterminer les ”symétries”. 2 3 1 4
9. Pour comprendre un graphe, on cherche à en déterminer les ”symétries”. 2 3 1 4 1 2 3 4 7→ 7 → 7 → 7 → 1 4 3 2
10. Pour comprendre un graphe, on cherche à en déterminer les ”symétries”. 2 3 1 4 1 2 3 4 7→ 7 → 7 → 7 → 1 4 3 2 1 2 3 4 7→ 7 → 7 → 7 → 3 2 1 4
11. Pour comprendre un graphe, on cherche à en déterminer les ”symétries”. 2 3 1 4 1 2 3 4 7→ 7 → 7 → 7 → 1 4 3 2 1 2 3 4 7→ 7 → 7 → 7 → 3 2 1 4 1 2 3 4 7→ 7 → 7 → 7 → 2 1 4 3
12. Pour comprendre un graphe, on cherche à en déterminer les ”symétries”. 2 3 1 4 1 2 3 4 7→ 7 → 7 → 7 → 1 4 3 2 1 2 3 4 7→ 7 → 7 → 7 → 3 2 1 4 1 2 3 4 7→ 7 → 7 → 7 → 2 1 4 3 1 2 3 4 7→ 7 → 7 → 7 → 4 3 2 1
13. Pour comprendre un graphe, on cherche à en déterminer les ”symétries”. 2 3 1 4 1 2 3 4 7→ 7 → 7 → 7 → 1 4 3 2 1 2 3 4 7→ 7 → 7 → 7 → 3 2 1 4 1 2 3 4 7→ 7 → 7 → 7 → 2 1 4 3 1 2 3 4 7→ 7 → 7 → 7 → 4 3 2 1 1 2 3 4 7→ 7 → 7 → 7 → 1 2 3 4 1 2 3 4 7→ 7 → 7 → 7 → 2 3 4 1 1 2 3 4 7→ 7 → 7 → 7 → 3 4 1 2 1 2 3 4 7→ 7 → 7 → 7 → 4 1 2 3
14. 2 3 1 4 1 2 3 4 7→ 7 → 7 → 7 → 1 4 3 2 1 2 3 4 7→ 7 → 7 → 7 → 3 2 1 4 1 2 3 4 7→ 7 → 7 → 7 → 2 1 4 3 1 2 3 4 7→ 7 → 7 → 7 → 4 3 2 1 1 2 3 4 7→ 7 → 7 → 7 → 1 2 3 4 1 2 3 4 7→ 7 → 7 → 7 → 2 3 4 1 1 2 3 4 7→ 7 → 7 → 7 → 3 4 1 2 1 2 3 4 7→ 7 → 7 → 7 → 4 1 2 3 Il faut donc une définition qui ne dépende pas du dessin mais seulement du graphe.
15. Définition. Un automorphisme d’un graphe G = (S, A) est une bijection f : S → S telle que, pour tous x, y ∈ S, {x, y} ∈ A ⇔ {f(x), f(y)} ∈ A. En d’autres termes, un automorphisme est une bijection de S dans S qui préserve les arêtes.
16. Proposition. L’ensemble des automorphismes d’un graphe est un groupe (fini) pour la composition ◦. On le note Aut(G) et on cherche à le déterminer à isomorphisme près. Intuitivement, plus le groupe des automorphismes est gros, plus le graphe admet de symétries.
17. Déterminons le groupe des automorphismes d’un graphe complet Kn à n sommets. 5 4 3 6 2 7 1 8 12 9 10 11
18. Déterminons le groupe des automorphismes d’un graphe complet Kn à n sommets. 5 4 3 6 2 7 1 8 12 9 10 11 Proposition. Le groupe Aut(Kn ) est isomorphe au groupe symétrique Sn .
19. Déterminons le groupe des automorphismes d’un graphe cycle Cn à n sommets. 5 4 3 6 2 7 1 8 12 9 10 11
20. Déterminons le groupe des automorphismes d’un graphe cycle Cn à n sommets. 5 4 3 6 2 7 1 8 12 9 Notons k = f(1) = k 10 11
21. Déterminons le groupe des automorphismes d’un graphe cycle Cn à n sommets. 5 4 3 6 2 7 1 8 12 9 Notons k = f(1) = k, 10 11 alors f(2) ∈ {k − 1, k + 1}
22. Déterminons le groupe des automorphismes d’un graphe cycle Cn à n sommets. 5 4 3 6 2 7 1 8 12 9 Notons k = f(1) = k, 10 11 alors f(2) ∈ {k − 1, k + 1} et les autres f(i) sont fixés.
23. Déterminons le groupe des automorphismes d’un graphe cycle Cn à n sommets. 5 4 3 6 2 7 1 8 12 9 Notons k = f(1) = k, 10 11 alors f(2) ∈ {k − 1, k + 1} et les autres f(i) sont fixés. Proposition. Le groupe Aut(Cn ) est isomorphe au groupe diédral Dn .
24. Proposition. Soit G un graphe et f ∈ Aut(G). Alors, • si x ∈ S est de degré d, alors f(x) est de degré d, • si x ∈ S admet un voisin y de degré d, alors f(x) admet un voisin de degré d, • s’il existe un chemin de longueur k entre x et y, alors il existe un chemin de longueur k entre f(x) et f(y). • pour tous x, y ∈ S, la distance entre f(x) et f(y) est égale à la distance entre x et y.
25. Proposition. Le groupe des automorphismes du graphe chemin à n sommets est isomorphe à 1 2 3 4 5 6 7 8 9
26. Proposition. Le groupe des automorphismes du graphe chemin à n sommets est isomorphe à Z/2Z. 1 2 3 4 5 6 7 8 9
27. Exercice. Soit f un automorphisme du graphe dont voici un dessin: 10 9 1 1. Pourquoi f(1) ∈ {1, 4}? 2. Pourquoi f(6) ∈ {6, 10}? 3. Pourquoi f(5) ∈ {5, 9}? 4. Pourquoi f(2) = 2? 5. Qui est f? 6 8 5 7 2 3 4
28. Proposition. Le groupe des automorphismes du graphe dont voici un dessin: 9 1 est {Id}. 6 8 5 7 2 3 4
29. Proposition. Le groupe des automorphismes du graphe de Frucht est {Id}. 4 3 5 2 11 6 1 12 7 10 8 9 Il s’agit donc d’un graphe à la fois très régulier (tous les sommets sont de même degré 3) et sans symétrie.
30. 4 3 5 2 11 6 1 12 7 10 8 9 8−9−10−12 est l’unique cycle de longueur 4 donc f({8, 9, 10, 12}) ⊂ {8, 9, 10, 12}.
31. 4 3 5 2 11 6 1 12 7 10 8 9 8−9−10−12 est l’unique cycle de longueur 4 donc f({8, 9, 10, 12}) ⊂ {8, 9, 10, 12}. 7−8−9 est envoyé sur l’un des trois triangles: f(7) = 7, f(8) ∈ {8, 9}, f(9) ∈ {8, 9}.
32. 4 3 5 2 11 6 1 12 7 10 8 9 8−9−10−12 est l’unique cycle de longueur 4 donc f({8, 9, 10, 12}) ⊂ {8, 9, 10, 12}. 7−8−9 est envoyé sur l’un des trois triangles: f(7) = 7, Ensuite, f(6) = 6. f(8) ∈ {8, 9}, f(9) ∈ {8, 9}.
33. 4 3 5 2 11 6 1 12 7 10 8 9 8−9−10−12 est l’unique cycle de longueur 4 donc f({8, 9, 10, 12}) ⊂ {8, 9, 10, 12}. 7−8−9 est envoyé sur l’un des trois triangles: f(7) = 7, f(8) ∈ {8, 9}, f(9) ∈ {8, 9}. Ensuite, f(6) = 6. 5−6−7−8−12−11 est envoyé sur l’un des quatre cycles de longueur 6: f(8) = 8, f(12) = 12, f(11) = 11, f(5) = 5.
34. 4 3 5 2 11 6 1 12 7 10 8 9 8−9−10−12 est l’unique cycle de longueur 4 donc f({8, 9, 10, 12}) ⊂ {8, 9, 10, 12}. 7−8−9 est envoyé sur l’un des trois triangles: f(7) = 7, f(8) ∈ {8, 9}, f(9) ∈ {8, 9}. Ensuite, f(6) = 6. 5−6−7−8−12−11 est envoyé sur l’un des quatre cycles de longueur 6: f(8) = 8, f(12) = 12, On poursuit de manière analogue... f(11) = 11, f(5) = 5.
35. Graphs of Degree Three with a Given Abstract Group, Robert Frucht (1949)
36. Proposition. Le groupe des automorphismes du graphe de Petersen est isomorphe à S5 . 2 3 7 8 6 9 1 10 4 5 Ce graphe est très régulier (tous les sommets sont de même degré 3) et admet beaucoup de symétries.
37. On a pour l’instant obtenu les groupes {Id}, Z/2Z, Dn , Sn ...
38. On a pour l’instant obtenu les groupes {Id}, Z/2Z, Dn , Sn ... ,→ Existe-t-il un graphe G tel que Aut(G) ≈ Z/3Z?
39. On a pour l’instant obtenu les groupes {Id}, Z/2Z, Dn , Sn ... ,→ Existe-t-il un graphe G tel que Aut(G) ≈ Z/3Z? ,→ Plus généralement, quels groupes finis sont des groupes d’automorphismes d’un graphe? Theorie der endlichen und unendlichen Graphen, Dénes Kőnig (1936), p.5
40. Robert Wertheimer Frucht dit Roberto, dit Toro • Né en 1906 à Brno • Thèse en algèbre en 1931 sous la direction de Issaï Schur à l’université de Berlin • Travaille comme actuaire dans une compagnie d’assurance à Trieste dans les années 30 • Découvre les graphes dans le livre de Dénes Kőnig en 1936 • Déménage en Argentine en 1938 puis au Chili où il s’installe définitivement • Carrière à l’Université technique Federico Santa María de Valparaíso • Décès en 1997
41. Théorème. Pour tout groupe fini H, il existe un graphe G tel que H ≈ Aut(G). Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Robert Frucht (1938)
42. Des groupes aux graphes Dans cette section, on part d’un groupe et on lui associe un graphe en deux temps.
43. Définition. Soit G un groupe fini. Une partie S ⊂ G est génératrice si G = hSi. Comme G est fini, cela donne la proposition suivante. Proposition. Soit G un groupe fini et S une partie génératrice. Alors, pour tout g ∈ G, on dispose de n ∈ N et de si1 , si2 , …sin ∈ S tels que g = si1 si2 · · · sin . Un groupe fini admet toujours une partie génératrice: G. Pour la suite, on cherche plutôt à utiliser une ”petite” partie génératrice. Voici quelques exemples de parties génératrices: • dans Z/nZ, {1} • dans Sn , {(1 2), (1 2 · · · n)} • dans PSL2 (F7 ), ( 0 1 −1 0   , 0 1 −1 1 )
44. Définition. Soit G un groupe fini et S = {s1 , . . . , sr } une partie génératrice. Le graphe de Cayley pour (G, S) est le graphe orienté avec des arêtes étiquetées par S défini par • l’ensemble des sommets est G, • il y a une arête étiquetée par sk de x vers y si y = xsk . x On le note Cay(G, S). sk y = xsk
45. 1 0 1 1 1 2 Cay(Z/3Z, {1})
46. (1 2) 1 0 1 1 (1 3) (1 2 3) Id 1 (1 3 2) 2 (2 3) Cay(Z/3Z, {1}) Cay(S3 , {(1 2), (1 2 3)})
47. (1 2) 1 0 1 (1 2 3) (1 3) (1 2) 1 (1 2) Id 1 (1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 3 2) 2 (1 2) (2 3) Cay(Z/3Z, {1}) Cay(S3 , {(1 2), (1 2 3)})
48. On généralise la notion d’automorphisme à un graphe orienté et étiqueté. Définition. Soit G un groupe fini muni d’une partie génératrice S. Un automorphisme du graphe Cay(G, S) est une bijection f : G → G telle que, pour tous x, y ∈ G et tout s ∈ S, il existe une arête de x vers y étiquetée par s si, et seulement si, il existe une arête de f(x) vers f(y) étiquetée par s. ∗ On le note Aut (Cay(G, S)) et on cherche à le déterminer (à isomorphisme près). ∗ Proposition. L’ensemble Aut (Cay(G, S)) est un groupe pour la composition ◦.
49. Proposition. Soit G un groupe fini muni d’une partie génératrice S. Alors, Aut∗ (Cay(G, S)) ≈ G.
50. Proposition. Soit G un groupe fini muni d’une partie génératrice S. Alors, Aut∗ (Cay(G, S)) ≈ G. ∗ Démonstration. Considérons l’application f : G → Aut (Cay(G, S)) définie par g 7→ (fg : x 7→ gx). Montrons successivement que ∗ 1. f est à valeurs dans Aut (Cay(G, S)), 2. f est un morphisme de groupes, 3. f est injective, 4. f est surjective.
51. ∗ 1. f est à valeurs dans Aut (Cay(G, S)) Fixons g ∈ G. Soit x, y ∈ G et s ∈ S, on rappelle qu’il existe une arête de x vers y étiquetée par s si, et seulement si, y = xs. Or, y = xs ⇔ gy = gxs ⇔ fg (y) = fg (x)s Ainsi, il existe une arête de x vers y étiquetée par s si, et seulement si, il existe une arête de fg (x) vers fg (y) étiquetée par s. En conclusion, pour tout g ∈ G, fg est bien un automorphisme du graphe Cay(G, S).
52. 2. f est un morphisme de groupes Soit g, h ∈ G. Alors, pour tout x ∈ G fgh (x) = (gh)x = ghx, fg ◦ fh (x) = fg (hx) = ghx. Par conséquent, fgh = fg ◦ fh .
53. 3. f est injective Soit g ∈ Kerf, c’est-à-dire fg = Id. Par conséquent, g = fg (e) = e. En conclusion, Kerf = {e} et f est injective.
54. 4. f est surjective ∗ Soit ϕ ∈ Aut (Cay(G, S)). Notons g = ϕ(e). Pour tout x ∈ G, on dispose de si1 , si2 , …sin ∈ S tels que x = si1 si2 · · · sin . Ainsi, ϕ(x) = ϕ((si1 si2 · · · sin−1 )sin ) = ϕ(si1 si2 · · · sin−1 )sin .. . = ϕ(e)si1 si2 · · · sin = gsi1 si2 · · · sin = fg (x). En conclusion, ϕ = fg .
55. On transforme le graphe Cay(G, S) en un graphe non orienté, non étiqueté Cay(G, S). Pour cela, on remplace chaque arête par un graphe ”gadget” dont la forme dépend de l’orientation et de l’étiquette de l’arête. x s1 y x y
56. On transforme le graphe Cay(G, S) en un graphe non orienté, non étiqueté Cay(G, S). Pour cela, on remplace chaque arête par un graphe ”gadget” dont la forme dépend de l’orientation et de l’étiquette de l’arête. x s2 y x y
57. On transforme le graphe Cay(G, S) en un graphe non orienté, non étiqueté Cay(G, S). Pour cela, on remplace chaque arête par un graphe ”gadget” dont la forme dépend de l’orientation et de l’étiquette de l’arête. x s3 y x y
58. On transforme le graphe Cay(G, S) en un graphe non orienté, non étiqueté Cay(G, S). Pour cela, on remplace chaque arête par un graphe ”gadget” dont la forme dépend de l’orientation et de l’étiquette de l’arête. x s4 y x y
59. Attention! L’ensemble des sommets de Cay(G, S) est G; celui de Cay(G, S) est beaucoup plus grand! De plus, dans Cay(G, S), on ne sait a priori pas distinguer les sommets qui étaient déjà dans Cay(G, S) de ceux qui ont été ajoutés par la transformation en graphe non orienté.
60. 1 0 1 1 1 2 Cay(Z/3Z, {1}) Cay(Z/3Z, {1})
61. Dans le graphe transformé, on distingue ··· ···
62. Dans le graphe transformé, on distingue • des sommets de degré 1 ··· ···
63. Dans le graphe transformé, on distingue • des sommets de degré 1 • des sommets de degré 2 avec au plus un voisin de degré 3 ··· ···
64. Dans le graphe transformé, on distingue • des sommets de degré 1 • des sommets de degré 2 avec au plus un voisin de degré 3 • des sommets de degré 3 ··· ···
65. Dans le graphe transformé, on distingue • des sommets de degré 1 • des sommets de degré 2 avec au plus un voisin de degré 3 • des sommets de degré 3 • des sommets de degré pair, 2|S|, dont tous les voisins sont de degré 3: ceux issus de G ··· ···
66. Proposition. Soit G un groupe fini muni d’une partie génératrice S, Cay(G, S) le graphe de Cayley associé et Cay(G, S) le graphe non orienté, non étiqueté qui en est déduit par les transformations précédentes. Alors, Aut(Cay(G, S)) ≈ Aut∗ (Cay(G, S)), et, par conséquent, Aut(Cay(G, S)) ≈ G.
67. Proposition. Soit G un groupe fini muni d’une partie génératrice S, Cay(G, S) le graphe de Cayley associé et Cay(G, S) le graphe non orienté, non étiqueté qui en est déduit par les transformations précédentes. Alors, Aut(Cay(G, S)) ≈ Aut∗ (Cay(G, S)), et, par conséquent, Aut(Cay(G, S)) ≈ G. Démonstration. Considérons l’application ϕ : Aut(Cay(G, S)) → Aut∗ (Cay(G, S)) qui à un automorphisme du graphe Cay(G, S) associe l’application induite sur G.
68. Soit f ∈ Aut(Cay(G, S)). Comme les sommets issus de G sont les seuls sommets de degré pair dont tous les voisins sont de degré 3, f envoie globalement ces sommets sur eux-mêmes: f(G) = G. Chaque chemin de longueur 3 entre deux sommets x et y de G dans Cay(G, S) correspond à un ”gadget” et l’on retrouve ce même ”gadget” entre f(x) et f(y). Cela signifie que dans Cay(G, S), l’arête qui relie x à y (ou y à x selon le gadget) est étiquetée comme l’arête qui relie f(x) à f(y) (ou f(y) à f(x)). Ainsi, l’induit par f sur G définit bien un automorphisme du graphe Cay(G, S). En conclusion, ϕ est bien défini.
69. On vérifie immédiatement qu’un automorphisme de Cay(G, S) se prolonge de manière unique en un automorphisme de Cay(G, S) en envoyant le gadget entre x et y sur le gadget entre f(x) et f(y)
70. On vérifie immédiatement qu’un automorphisme de Cay(G, S) se prolonge de manière unique en un automorphisme de Cay(G, S) en envoyant le gadget entre x et y sur le gadget entre f(x) et f(y)
71. On vérifie immédiatement qu’un automorphisme de Cay(G, S) se prolonge de manière unique en un automorphisme de Cay(G, S) en envoyant le gadget entre x et y sur le gadget entre f(x) et f(y)
72. On vérifie immédiatement qu’un automorphisme de Cay(G, S) se prolonge de manière unique en un automorphisme de Cay(G, S) en envoyant le gadget entre x et y sur le gadget entre f(x) et f(y)
73. Théorème. Tout groupe fini est le groupe des automorphismes d’un graphe (non orienté).
74. Conclusion La preuve de Frucht résout la question de départ avec une méthode constructive... mais, comme souvent en mathématique, cela amène d’autres questions: • peut-on déterminer le plus petit graphe associé à un groupe donné? • peut-on imposer des propriétés supplémentaires sur le graphe associé à un groupe donné?
75. Voici par exemple le graphe transformé Cay(S3 , {(1 2), (1 2 3)})
76. Voici par exemple le graphe transformé Cay(S3 , {(1 2), (1 2 3)}) et ses 84 sommets...
77. Cet exemple est loin d’être minimal... car on a déjà établi que S3 est isomorphe au groupe des automorphismes du triangle.