FindCycle[g] finds a list of vertices that define a cycle in graph g.

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

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.

FiniteGraphs produces a convenient list of all the interesting, finite, parameterless graphs built into Combinatorica.

HerschelGraph returns a graph object that represents a Herschel graph.

GraphRadius[g] gives the minimum eccentricity of the vertices in the graph g.

ShowGraphArray[{g_1, g_2, ...}] displays a row of graphs. ShowGraphArray[{{g_1, ...}, {g_2, ...}, \ ...}] displays a two-dimensional table of graphs.

AlternatingPaths[g, start, ME] returns the alternating paths in graph g with respect to the matching ME, starting at the vertices in the list start. The paths are returned in ...

Diameter[g] gives the diameter of graph g, the maximum length, among all pairs of vertices in g, of a shortest path between each pair.

EdgeColoring[g] uses Brelaz's heuristic to find a good, but not necessarily minimal, edge coloring of graph g.