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

GroetzschGraph returns the smallest triangle-free graph with chromatic number 4. This is identical to MycielskiGraph[4].

HeawoodGraph returns a smallest (6, 3)-cage, a 3-regular graph with girth 6.

IndependentSetQ[g, i] yields True if the vertices in list i define an independent set in graph g.

InduceSubgraph[g, s] constructs the subgraph of graph g induced by the list of vertices s.

IntervalGraph[l] constructs the interval graph defined by the list of intervals l.

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.