is_perfect_matching

is_perfect_matching(G, matching)

Return True if matching is a perfect matching for G

A perfect matching in a graph is a matching in which exactly one edge is incident upon each vertex.

Parameters:

GNetworkX graph

matchingdict or set

A dictionary or set representing a matching. If a dictionary, it must have matching[u] == v and matching[v] == u for each edge (u, v) in the matching. If a set, it must have elements of the form (u, v), where (u, v) is an edge in the matching.

Returns:

bool

Whether the given set or dictionary represents a valid perfect matching in the graph.

Examples

>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6)])
>>> my_match = {1: 2, 3: 5, 4: 6}
>>> nx.is_perfect_matching(G, my_match)
True