Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
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 : set
A maximal matching of the graph.
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.