MinimumSpanningTree[g] uses Kruskal's algorithm to find a minimum spanning tree of graph g.

TopologicalSort[g] gives a permutation of the vertices of the directed acyclic graph g such that an edge (i, j) implies that vertex i appears before vertex j.

PermuteSubgraph[g, p] permutes the vertices of a subgraph of g induced by p according to p.

Wheel[n] constructs a wheel on n vertices, which is the join of CompleteGraph[1] and Cycle[n - 1].

FromAdjacencyMatrix[m] constructs a graph from a given adjacency matrix m, using a circular embedding. FromAdjacencyMatrix[m, v] uses v as the embedding for the resulting ...

SymmetricQ[r] tests if a given square matrix r represents a symmetric relation. SymmetricQ[g] tests if the edges of a given graph represent a symmetric relation.

AddEdges[g, edgeList] gives graph g with the new edges in edgeList added. edgeList can have the form {a, b} to add a single edge {a, b} or the form {{a, b}, {c, d}, ...}, to ...

MinimumVertexColoring[g] returns a minimum vertex coloring of g. MinimumVertexColoring[g, k] returns a k-coloring of g, if one exists.

UnionSet[a, b, s] merges the sets containing a and b in union-find data structure s.

PageRankVector[g] returns the page rank of the graph g.