graphe de Frucht

Le graphe de Frucht est, en théorie des graphes, un graphe 3-régulier possédant 12 sommets et 18 arêtes. C'est le plus petit graphe cubique dont le groupe d'automorphismes ne contienne que l'élément neutre. En d'autre termes, c'est le plus petit graphe régulier de degré trois étant un graphe asymétrique. Il est décrit pour la première fois en 1939 par Robert Frucht, d'où son nom.