Graphe de DesarguesEn théorie des graphes, le graphe de Desargues est un graphe cubique symétrique possédant 20 sommets et 30 arêtes. Il doit son nom à Girard Desargues. Le graphe de Desargues est isomorphe au graphe biparti de Kneser et au graphe généralisé de Petersen GP(10,3). C'est aussi le graphe d'incidence de la configuration de Desargues. Le graphe de Desargues est hamiltonien et peut être décrit par la notation LCF : [5, −5, 9, −9]5.
Graphe polyédriqueEn théorie des graphes, une branche des mathématiques, un graphe polyédrique est un graphe non orienté défini en termes géométriques : il représente les sommets et les arêtes d'un polyèdre convexe. On peut aussi définir un graphe polyédrique en termes purement issus de la théorie des graphes : c'est un graphe planaire 3 sommet-connexe. Le diagramme de Schlegel d'un polyèdre convexe représente ses sommets et ses arêtes par des points et des segments de droite dans le plan euclidien.
Graphe semi-symétriqueEn théorie des graphes, un graphe non-orienté est semi-symétrique s'il est arête-transitif et régulier, mais pas sommet-transitif. Autrement dit, un graphe est semi-symétrique s'il est régulier et si son groupe d'automorphismes agit transitivement sur ses arêtes, mais pas sur ses sommets. Tout graphe semi-symétrique est biparti, et son groupe d'automorphisme agit transitivement sur les deux sous-ensembles de sommets de la bipartition. Il n'existe aucun graphe semi-symétrique d'ordre 2p ou 2p, où p est un nombre premier.
Théorème de VizingLe théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Il est dû à Vadim G. Vizing. Une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. On note χ′(G) le nombre minimum de couleur nécessaire pour avoir une coloration des arêtes.
Graphe biparti completEn théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de est relié à chaque sommet de . Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté . Si m = 1, le graphe complet biparti K1,n est une étoile et est noté .
