MaximumMatching(G) returns a set of edges corresponding to a matching of maximum size for the given graph G.

MatchingNumber(G) returns an integer corresponding to the size of a maximum matching for G.

A matching of G, also called an independent edge set, is a subset of the edges of G with the property that no edges in the matching share a common vertex. A matching in which every vertex of G appears in some edge is called a perfect matching.

The strategy employed is the blossom algorithm (see Edmonds, 1965).

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$H≔\mathrm{SpecialGraphs}:-\mathrm{HypercubeGraph}\left(3\right)$

$H≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 8\; vertices\; and\; 12\; edge(s)}$

$M≔\mathrm{MaximumMatching}\left(H\right)$

$M≔\left\{\left\{''000''\,''001''\right\}\,\left\{''010''\,''011''\right\}\,\left\{''100''\,''101''\right\}\,\left\{''110''\,''111''\right\}\right\}$

$\mathrm{HighlightEdges}\left(H\,M\,\mathrm{red}\right)$

$\mathrm{DrawGraph}\left(H\right)$

$G≔\mathrm{SpecialGraphs}:-\mathrm{SoccerBallGraph}\left(\right)$

$G≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 60\; vertices\; and\; 90\; edge(s)}$

$M≔\mathrm{MaximumMatching}\left(G\right)$

$M≔\left\{\left\{1\,2\right\}\,\left\{3\,4\right\}\,\left\{5\,26\right\}\,\left\{6\,7\right\}\,\left\{8\,9\right\}\,\left\{10\,12\right\}\,\left\{11\,15\right\}\,\left\{13\,14\right\}\,\left\{16\,17\right\}\,\left\{18\,19\right\}\,\left\{20\,22\right\}\,\left\{21\,25\right\}\,\left\{23\,24\right\}\,\left\{27\,28\right\}\,\left\{29\,30\right\}\,\left\{31\,32\right\}\,\left\{33\,34\right\}\,\left\{35\,56\right\}\,\left\{36\,37\right\}\,\left\{38\,39\right\}\,\left\{40\,42\right\}\,\left\{41\,45\right\}\,\left\{43\,44\right\}\,\left\{46\,47\right\}\,\left\{48\,49\right\}\,\left\{50\,52\right\}\,\left\{51\,55\right\}\,\left\{53\,54\right\}\,\left\{57\,58\right\}\,\left\{59\,60\right\}\right\}$

$\mathrm{HighlightEdges}\left(G\,M\,\mathrm{red}\right)$

$\mathrm{DrawGraph}\left(G\right)$

Edmonds, Jack. "Paths, trees, and flowers." Canad. J. Math., 17(1965), 449-467. doi:10.4153/CJM-1965-045-4

The GraphTheory[MatchingNumber] and GraphTheory[MaximumMatching] commands were introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016.