FranklinGraph returns a 12-vertex graph that represents a 6-chromatic map on the Klein bottle. It is the sole counterexample to Heawood's map-coloring conjecture.

Harary[k, n] constructs the minimal k-connected graph on n vertices.

Involutions[l] gives the list of involutions of the elements in the list l. Involutions[l, Cycles] gives the involutions in their cycle representation. Involution[n] gives ...

MeredithGraph returns a 4-regular, 4-connected graph that is not Hamiltonian, providing a counterexample to a conjecture by C. St. J. A. Nash\[Dash]Williams.

OddGraph[n] returns the graph whose vertices are the size-(n - 1) subsets of a size-(2 nTraditionalForm\`\[Dash]1) set and whose edges connect pairs of vertices that ...

PetersenGraph returns the Petersen graph, a graph whose vertices can be viewed as the size-2 subsets of a size-5 set with edges connecting disjoint subsets.

SetEdgeLabels[g, l] assigns the labels in l to edges of g.

SetVertexLabels[g, l] assigns the labels in l to vertices of g.

ThomassenGraph returns a hypotraceable graph, a graph G that has no Hamiltonian path but whose subgraph G - v for every vertex v has a Hamiltonian path.

Turan[n, p] constructs the Turán graph, the extremal graph on n vertices that does not contain CompleteGraph[p].