ChromaticPolynomial[g, z] gives the chromatic polynomial P(z) of graph g, which counts the number of ways to color g with, at most, z colors.

CodeToLabeledTree[l] constructs the unique labeled tree on n vertices from the Prüfer code l, which consists of a list of n - 2 integers between 1 and n.

Compositions[n, k] gives a list of all compositions of integer n into k parts.

CoxeterGraph gives a non-Hamiltonian graph with a high degree of symmetry such that there is a graph automorphism taking any path of length 3 to any other.

CycleIndex[pg, x] returns the polynomial in x[1], x[2], ..., x[index[pg]] that is the cycle index of the permutation group pg. Here index[pg] refers to the length of each ...

DilateVertices[v, d] multiplies each coordinate of each vertex position in list v by d, thus dilating the embedding. DilateVertices[g, d] dilates the embedding of graph g by ...

Eccentricity[g] gives the eccentricity of each vertex v of graph g, the maximum length among all shortest paths from v.

EdgeChromaticNumber[g] gives the fewest number of colors necessary to color each edge of graph g, so that no two edges incident on the same vertex have the same color.

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

GraphJoin[g_1, g_2, ...] constructs the join of graphs g_1, g_2, and so on. This is the graph obtained by adding all possible edges between different graphs to the graph ...