12-cage de TutteLa 12-cage de Tutte est, en théorie des graphes, un graphe 3-régulier possédant 126 sommets et 189 arêtes. Le diamètre de la 12-cage de Tutte, l'excentricité maximale de ses sommets, est 6, son rayon, l'excentricité minimale de ses sommets, est 6 et sa maille, la longueur de son plus court cycle, est 12. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
Graphe de GrayLe graphe de Gray est, en théorie des graphes, un graphe 3-régulier possédant 54 sommets et 81 arêtes. Il tire son nom de Marion Cameron Gray qui le découvrit en 1932 ; il fut publié pour la première fois par I. Z. Bouwer en 1968. Le diamètre du graphe de Gray, l'excentricité maximale de ses sommets, est 6, son rayon, l'excentricité minimale de ses sommets, est 6 et sa maille, la longueur de son plus court cycle, est 8.
Snark de SzekeresLe snark de Szekeres est, en théorie des graphes, un graphe 3-régulier possédant 50 sommets et 75 arêtes. Le diamètre du snark de Szekeres, l'excentricité maximale de ses sommets, est 7, son rayon, l'excentricité minimale de ses sommets, est 6 et sa maille, la longueur de son plus court cycle, est 5. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
Lemme des poignées de mainvignette|250px|Dans ce graphe, un nombre pair de sommets (les quatre sommets numérotés 2, 4, 5, et 6) a des degrés impairs. La somme des degrés des sommets vaut 2 + 3 + 2 + 3 + 3 + 1 = 14, deux fois le nombre d'arêtes. En théorie des graphes, une branche des mathématiques, le lemme des poignées de main est la déclaration selon laquelle chaque graphe non orienté fini a un nombre pair de sommets de degré impair. Plus trivialement, dans une réunion de plusieurs personnes dont certaines se serrent la main, un nombre pair de personnes devra serrer un nombre impair de fois la main d'autres personnes.
Linkless embeddingIn topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.
Théorème de BrooksEn mathématiques, et plus particulièrement dans la théorie des graphes, le théorème de Brooks donne une relation entre le degré maximal d'un graphe connexe non orienté et son nombre chromatique. Selon ce théorème, dans un graphe où chaque sommet a au plus Δ voisins, les sommets peuvent être colorés avec au plus Δ couleurs, sans que deux sommets adjacents n'aient la même couleur, sauf dans deux cas, les graphes complets et les graphes cycles de longueur impaire, qui ont besoin de Δ + 1 couleurs.
Graphe intégralEn théorie des graphes, un graphe intégral est un graphe dont le spectre de la matrice d'adjacence ne contient que des entiers (relatifs). En d'autres termes, les racines de son polynôme caractéristique sont toutes entières. Leur étude fut introduite par Harary et Schwenk en 1974. Le plus petit graphe intégral est le graphe singleton. Aux ordres 1, 2 et 3 il existe un unique graphe connexe intégral. Il existe 2 graphes connexes intégraux distincts à isomorphisme près à l'ordre 4, 3 à l'ordre 5, 6 à l'ordre 6, 7 à l'ordre 7, 22 à l'ordre 8, 24 à l'ordre 9 et 83 à l'ordre 10.
Graphe asymétriquethumb|Les huit graphes asymétriques à 6 sommets En théorie des graphes, un graphe asymétrique ou graphe identité est un graphe dont le groupe d'automorphismes est trivial. C'est donc un graphe n'admettant aucun automorphisme autre que l'identité. Le plus petit graphe asymétrique est le graphe singleton, qui est également un graphe symétrique. Si on exclut ce cas trivial, un graphe asymétrique doit avoir au moins 6 sommets. Il existe 8 graphes asymétriques distincts à isomorphisme près à l'ordre 6, 152 à l'ordre 7, à l'ordre 8, à l'ordre 9, à l'ordre 10 et à l'ordre 11.
Partial cubeIn graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels.
Bipartite double coverIn graph theory, the bipartite double cover of an undirected graph G is a bipartite, covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K_2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G. It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice. The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G.
