Skip to main content
`Ctrl`+`K`

# maximal_matching

maximal_matching(G)

  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

  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.

  Examples

      >>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)])
      >>> sorted(nx.maximal_matching(G))
      [(1, 2), (3, 5)]