MakeSimple[g] gives the undirected graph, free of multiple edges and self-loops derived from graph g.
MaximalMatching[g] gives the list of edges associated with a maximal matching of graph g.
MaximumAntichain[g] gives a largest set of unrelated vertices in partial order g.
MaximumIndependentSet[g] finds a largest independent set of graph g.
MaximumSpanningTree[g] uses Kruskal's algorithm to find a maximum spanning tree of graph g.
McGeeGraph returns the unique (7, 3)-cage, a 3-regular graph with girth 7.
MinimumChainPartition[g] partitions partial-order g into a minimum number of chains.
MinimumChangePermutations[l] constructs all permutations of list l such that adjacent permutations differ by only one transposition.
MinimumVertexColoring[g] returns a minimum vertex coloring of g. MinimumVertexColoring[g, k] returns a k-coloring of g, if one exists.
MultipleEdgesQ[g] yields True if g has multiple edges between pairs of vertices. It yields False otherwise.