VertexCoverQ[g, vlist] yields True if the vertex list vlist is a vertex cover of the graph g, and False otherwise.

BipartiteMatchingAndCover[g] takes a bipartite graph g and returns a matching with maximum weight along with the dual vertex cover. If the graph is not weighted, it is ...

BipartiteMatching[g] gives the list of edges associated with a maximum matching in bipartite graph g. If the graph is edge weighted, then the function returns a matching with ...

InDegree[g, n] returns the in-degree of vertex n in directed graph g. InDegree[g] returns the sequence of in-degrees of the vertices in directed graph g.

OrientGraph[g] assigns a direction to each edge of a bridgeless, undirected graph g, so that the graph is strongly connected.

OutDegree[g, n] returns the out-degree of vertex n in directed graph g. OutDegree[g] returns the sequence of out-degrees of the vertices in directed graph g.

TwoColoring[g] finds a two-coloring of graph g if g is bipartite. It returns a list of the labels 1 and 2 corresponding to the vertices.

FindIndependentEdgeSet[g] finds an independent edge set of the graph g with a maximum number of edges.

GraphUnion[g_1, g_2, ...] constructs the union of graphs g_1, g_2, and so forth. GraphUnion[n, g] constructs n copies of graph g, for any nonnegative integer n.

NonLineGraphs returns a graph whose connected components are the 9 graphs whose presence as a vertex-induced subgraph in a graph g makes g a nonline graph.