Graphe de Dürer

Le graphe de Dürer est ainsi nommé en référence au polyèdre représenté dans la Melencolia de Albrecht Dürer. C'est donc le squelette d'un rhomboèdre tronqué en deux de ses coins opposés. Ce solide possède, comme le graphe, six faces pentagonales et deux faces triangulaires.

On peut aussi plus simplement le considérer comme le squelette d'un cube tronqué en deux de ses coins opposés.

Le graphe de Dürer est aussi un cas de graphe de Petersen généralisé : il ressemble au graphe de Petersen en ce qu'on peut le dessiner avec un motif en étoile au centre et un motif en polygone régulier à l'extérieur, mais avec six sommets dans chaque motif au lieu de cinq.

Le diamètre du graphe de Dürer, l'excentricité maximale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 3-sommet-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets.

Le nombre chromatique du graphe de Dürer est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du graphe de Dürer est 3. Il existe donc une 3-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Le groupe d'automorphismes du graphe de Dürer est un groupe d'ordre 12 isomorphe au groupe diédral D₆, le groupe des isométries du plan conservant un hexagone régulier. Ce groupe est constitué de 6 éléments correspondant aux rotations et de 6 autres correspondant aux réflexions.

• Théorie des graphes

• (en) Eric W. Weisstein, Dürer's Graph (MathWorld)