ApproximateVertexCover[g] produces a vertex cover of graph g whose size is guaranteed to be within twice the optimal size.

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

ExactRandomGraph[n, e] constructs a random labeled graph of exactly e edges and n vertices.

FolkmanGraph returns a smallest graph that is edge-transitive but not vertex-transitive.

GrayGraph returns a 3-regular, 54-vertex graph that is edge-transitive but not vertex-transitive\[LongDash]the smallest known such example.

LeviGraph returns the unique (8, 3)-cage, a 3-regular graph whose girth is 8.

MaximumIndependentSet[g] finds a largest independent set of graph g.

McGeeGraph returns the unique (7, 3)-cage, a 3-regular graph with girth 7.

MycielskiGraph[k] returns a triangle-free graph with chromatic number k, for any positive integer k.

RegularQ[g] yields True if g is a regular graph.