diff --git a/swh/graph/tests/test_api_client.py b/swh/graph/tests/test_api_client.py
--- a/swh/graph/tests/test_api_client.py
+++ b/swh/graph/tests/test_api_client.py
@@ -138,11 +138,12 @@
     assert set(actual) == set(expected)
 
 
-def test_visit_edges_limited(graph_client):
+@pytest.mark.parametrize("max_edges", [1, 2, 3, 4, 5])
+def test_visit_edges_limited(graph_client, max_edges):
     actual = list(
         graph_client.visit_edges(
             "swh:1:rel:0000000000000000000000000000000000000010",
-            max_edges=4,
+            max_edges=max_edges,
             edges="rel:rev,rev:rev,rev:dir",
         )
     )
@@ -164,10 +165,11 @@
             "swh:1:dir:0000000000000000000000000000000000000002",
         ),
     ]
-    # As there are four valid answers (up to reordering), we cannot check for
-    # equality. Instead, we check the client returned all edges but one.
+    # As there are multiple valid answers for every value of max_edges (<= 3),
+    # we cannot check for equality.
+    # Instead, we check the client returned all edges but one.
     assert set(actual).issubset(set(expected))
-    assert len(actual) == 3
+    assert len(actual) == max_edges - 1
 
 
 def test_visit_edges_diamond_pattern(graph_client):