maximal_matching¶

maximal_matching(G)[source]¶

Find a maximal cardinality matching in the graph.

A matching is a subset of edges in which no node occurs more than once. The cardinality of a matching is the number of matched edges.

Parameters:	G (NetworkX graph) – Undirected graph
Returns:	matching – A maximal matching of the graph.
Return type:	set

Notes

The algorithm greedily selects a maximal matching M of the graph G (i.e. no superset of M exists). It runs in $O(|E|)$ time.