MeredithGraph returns a 4-regular, 4-connected graph that is not Hamiltonian, providing a counterexample to a conjecture by C. St. J. A. Nash\[Dash]Williams.

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.

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

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

MinimumVertexCover[g] finds a minimum vertex cover of graph g.

M[g] gives the number of edges in the graph g. M[g, Directed] is obsolete because M[g] works for directed as well as undirected graphs.

MultipleEdgesQ[g] yields True if g has multiple edges between pairs of vertices. It yields False otherwise.

MultiplicationTable[l, f] constructs the complete transition table defined by the binary relation function f on the elements of list l.

MycielskiGraph[k] returns a triangle-free graph with chromatic number k, for any positive integer k.