Échelle de Möbius
Dans la théorie des graphes, une branche des mathématiques, l'échelle de Möbius est un graphe cubique formé à partir du graphe cycle à sommets en ajoutant des arêtes entre les sommets opposés du cycle. Les graphes de cette famille sont nommés ainsi car, si l'on excepte , possède exactement cycles à 4 sommets qui, mis ensemble par leurs sommets partagés, forment l'équivalent d'un ruban de Möbius. Les échelles de Möbius ont été nommées et étudiées pour la première fois par Richard Guy et Frank Harary en 1967. vignette|Une vue de mettant en évidence sa ressemblance avec un ruban de Möbius vignette|L'échelle de Möbius sur un ruban de Möbius. vignette|Coloration avec 3 couleurs de . Les échelles de Möbius sont des graphes circulants. Elles ne sont pas des graphes planaires, mais peuvent être rendues planaires en supprimant un seul sommet, ce qui en fait des . Il est possible de le dessiner sur un plan avec un seul croisement et ce nombre est minimal. Il peut être dans un tore ou un plan projectif sans croisements, il s'agit donc d'exemple de graphe toroïdal. De-Ming Li a exploré des plongements de ces graphes sur des surfaces d'ordre supérieur. Les échelles de Möbius sont sommet-transitives mais ne sont pas arête-transitives (sauf ) : chaque montant de l'échelle appartient à un seul cycle de 4 sommets, tandis que les barreaux de l'échelle appartiennent chacun à deux de ces cycles. Le théorème de Brooks et le fait que le graphe soit cubique garantissent que 3 couleurs suffisent à le colorer. De fait, quand est pair, on a besoin des trois couleurs, et dans le cas contraire deux couleurs suffisent. De plus, les échelles de Möbius sont déterminées de façon unique par leurs polynômes chromatiques. L'échelle de Möbius possède 392 arbres couvrants. Elle et ont le plus d'arbres couvrants parmi tous les graphes cubiques ayant le même nombre de sommets. Ce n'est toutefois pas général. En effet, le graphe cubique à 10 sommet ayant le plus d'arbres couvrants est le graphe de Petersen, qui n'est pas une échelle de Möbius.
