Verify edges are valid in is_matching() (#4638)

* Verify edges are valid in is_matching()

Previously the is_matching() function was never checking the edges in
the provided matching against the graph, it would just validate there
were no shared endpoints. The graph object passed in to the function was
never used. This commit updates the function to check that all the edges
in the matching are valid and present in the provided graph before
checking if the are no shared endpoints.

Co-authored-by: Dan Schult <dschult@colgate.edu>

2 files changed, 15 insertions, 0 deletions

diff --git a/networkx/algorithms/matching.py b/networkx/algorithms/matching.py
index c6e5fd1c..4bcd9236 100644
--- a/networkx/algorithms/matching.py
+++ b/networkx/algorithms/matching.py
@@ -92,6 +92,13 @@ def is_matching(G, matching):
     """
     if isinstance(matching, dict):
         matching = matching_dict_to_set(matching)
+
+    for edge in matching:
+        if len(edge) != 2:
+            return False
+        if not G.has_edge(*edge):
+            return False
+
     # TODO This is parallelizable.
     return all(len(set(e1) & set(e2)) == 0 for e1, e2 in combinations(matching, 2))
 
diff --git a/networkx/algorithms/tests/test_matching.py b/networkx/algorithms/tests/test_matching.py
index 5886ed64..df9b8aba 100644
--- a/networkx/algorithms/tests/test_matching.py
+++ b/networkx/algorithms/tests/test_matching.py
@@ -408,6 +408,14 @@ class TestIsMatching:
         G = nx.path_graph(4)
         assert not nx.is_matching(G, {(0, 1), (1, 2), (2, 3)})
 
+    def test_invalid_edge(self):
+        G = nx.path_graph(4)
+        assert not nx.is_matching(G, {(0, 3), (1, 2)})
+        assert not nx.is_matching(G, {(0, 4)})
+        G = nx.path_graph(4, create_using=nx.DiGraph)
+        assert nx.is_matching(G, {(0, 1)})
+        assert not nx.is_matching(G, {(1, 0)})
+
 
 class TestIsMaximalMatching:
     """Unit tests for the