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.

Girth[g] gives the length of a shortest cycle in a simple graph g.

GraphicQ[s] yields True if the list of integers s is a graphic sequence, and thus represents a degree sequence of some graph.

HamiltonianQ[g] yields True if there exists a Hamiltonian cycle in graph g, or in other words, if there exists a cycle that visits each vertex exactly once.

LoopPosition is an option to ShowGraph whose values tell ShowGraph where to position a loop around a vertex. This option can take on values UpperLeft, UpperRight, LowerLeft, ...

NormalizeVertices[v] gives a list of vertices with a similar embedding as v but with the coordinates of all points scaled to be between 0 and 1.

OrientGraph[g] assigns a direction to each edge of a bridgeless, undirected graph g, so that the graph is strongly connected.

PerfectQ[g] yields True if g is a perfect graph, meaning that for every induced subgraph of g the size of a largest clique equals the chromatic number.

PermutationWithCycle[n, {i, j, ...}] gives a size-n permutation in which {i, j, ...} is a cycle and all other elements are fixed points.

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.