Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# networkx.algorithms.matching.maximal_matching¶

maximal_matching(G)[source]

Find a maximal matching in the graph.

A matching is a subset of edges in which no node occurs more than once. A maximal matching cannot add more edges and still be a matching.

Parameters: G (NetworkX graph) – Undirected graph matching – A maximal matching of the graph. 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.