CageGraph[k, r] gives a smallest k-regular graph of girth r for certain small values of k and r. CageGraph[r] gives CageGraph[3, r]. For k = 3, r can be 3, 4, 5, 6, 7, 8, or ...

CartesianProduct[l_1, l_2] gives the Cartesian product of lists l_1 and l_2.

ChangeEdges[g, e] replaces the edges of graph g with the edges in e. e can have the form {{s_1, t_1}, {s_2, t_2}, ...} or the form {{{s_1, t_1}, gr_1}, {{s_2, t_2}, gr_2}, ...

ChangeVertices[g, v] replaces the vertices of graph g with the vertices in the given list v. v can have the form {{x_1, y_1}, {x_2, y_2}, ...} or the form {{{x_1, y_1}, ...

ChromaticNumber[g] gives the chromatic number of the graph, which is the fewest number of colors necessary to color the graph.

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.

ChvatalGraph returns a smallest triangle-free, 4-regular, 4-chromatic graph.

CirculantGraph[n, l] constructs a circulant graph on n vertices, meaning the i\[Null]^th vertex is adjacent to the (i + j)\[Null]^th and (i - j)\[Null]^th vertices, for each ...

CircularEmbedding[n] constructs a list of n points equally spaced on a circle. CircularEmbedding[g] embeds the vertices of g equally spaced on a circle.

CliqueQ[g, c] yields True if the list of vertices c defines a clique in graph g.