A matching in a graph G is a subset M of the edges of G such that no two share an endpoint.
An oddset cover OSC of G is a labeling of the nodes of G with nonnegative integers such that every edge of G (which is not a selfloop) is either incident to a node labeled 1 or connects two nodes labeled with the same i , i > = 2 .
Let n_{i} be the number of nodes labeled i and consider any matching N . For i , i > = 2 , let N_{i} be the edges in N that connect two nodes labeled i . Let N_{1} be the remaining edges in N . Then  N_{i} < = n_{i}/2 and  N_{1} < = n_{1} and hence
It can be shown that for a maximum cardinality matching M there is always an oddset cover OSC with
list< edge>  MAX_CARD_MATCHING(const graph& G, node_array< int> & OSC, int heur = 0)  
computes a maximum cardinality matching M
in G
and
returns it as a list of edges.
The algorithm ([26], [38]) has running
time
O(nm*(n, m))
.
With
heur = 1
the algorithm uses a greedy heuristic
to find an initial matching.
This seems to have little effect on the running time of the algorithm.
An oddset cover that proves the maximality of M is returned in OSC.


list< edge>  MAX_CARD_MATCHING(const graph& G, int heur = 0)  
as above, but no proof of optimality is returned.  
bool  CHECK_MAX_CARD_MATCHING(const graph& G, const list< edge> & M, const node_array< int> & OSC)  
checks whether M is a maximum cardinality matching in G and OSC is a proof of optimality. Aborts if this is not the case. 