diff --git a/networkx/algorithms/connectivity/kcutsets.py b/networkx/algorithms/connectivity/kcutsets.py
index 2ad8bdfb4..c3457139a 100644
--- a/networkx/algorithms/connectivity/kcutsets.py
+++ b/networkx/algorithms/connectivity/kcutsets.py
@@ -3,6 +3,7 @@
 Kanevsky all minimum node k cutsets algorithm.
 """
 from operator import itemgetter
+from itertools import combinations
 
 import networkx as nx
 from .utils import build_auxiliary_node_connectivity
@@ -86,6 +87,22 @@ def all_node_cuts(G, k=None, flow_func=None):
     if not nx.is_connected(G):
         raise nx.NetworkXError('Input graph is disconnected.')
 
+    # Addess some corner cases first.
+    # For cycle graphs
+    if G.order() == G.size():
+        if all(2 == d for n, d in G.degree()):
+            seen = set()
+            for u in G:
+                for v in nx.non_neighbors(G, u):
+                    if (u, v) not in seen and (v, u) not in seen:
+                        yield {v, u}
+                        seen.add((v, u))
+            return
+    # For complete Graphs
+    if nx.density(G) == 1:
+        for cut_set in combinations(G, len(G)-1):
+            yield set(cut_set)
+        return
     # Initialize data structures.
     # Keep track of the cuts already computed so we do not repeat them.
     seen = []

all_node_cuts returns too few and incorrect cuts.
This could be a documentation issue, a bug or a user understanding issue. Are these cases pathological for the algorithm?

Given a square graph:

     a -- b
     |    |
     c -- d

Based on a cursory reading of the documentation, I would have expected all_node_cuts() to return:

    [{'a','d'}, {'c','b'}]

I get `[{'a','c'}]` but if this is a valid node cut then surely {a,b}, {b,d}, {c,d} are also equally valid and a function called "all node cuts" should return them. 

    G = nx.Graph([('a','b'), ('a','c'), ('c','d'), ('b','d')])
    print( G.nodes() )
    print( G.edges() )
    print( list(nx.all_node_cuts(G)) )

    >>> ['a', 'c', 'b', 'd']
    >>> [('a', 'c'), ('a', 'b'), ('c', 'd'), ('b', 'd')]
    >>> [{'a', 'c'}]

Expanding to a hexagon, we see similar pattern of node cuts. There are many isometric node cuts omitted from the results list. Two of the proposed cuts fail to create "two or more connected components" as the documentation suggests.

    G = nx.Graph([('a','b'), ('b','c'), ('c','d'),('d','e'), ('e','f'),('f','a')])
    list(nx.all_node_cuts(G))
    >>> [{'a', 'c'}, {'a', 'b'}, {'b', 'c'}]

diff --git a/networkx/algorithms/connectivity/tests/test_kcutsets.py b/networkx/algorithms/connectivity/tests/test_kcutsets.py
index e11547faf..9ca49698a 100644
--- a/networkx/algorithms/connectivity/tests/test_kcutsets.py
+++ b/networkx/algorithms/connectivity/tests/test_kcutsets.py
@@ -241,3 +241,27 @@ def test_non_repeated_cuts():
     assert_true(len(solution) == len(cuts))
     for cut in cuts:
         assert_true(cut in solution)
+
+
+def test_cycle_graph():
+    G = nx.cycle_graph(5)
+    solution = [{0, 2}, {0, 3}, {1, 3}, {1, 4}, {2, 4}]
+    cuts = list(nx.all_node_cuts(G))
+    assert_true(len(solution) == len(cuts))
+    for cut in cuts:
+        assert_true(cut in solution)
+
+
+def test_complete_graph():
+    G = nx.complete_graph(5)
+    solution = [
+        {0, 1, 2, 3},
+        {0, 1, 2, 4},
+        {0, 1, 3, 4},
+        {0, 2, 3, 4},
+        {1, 2, 3, 4},
+    ]
+    cuts = list(nx.all_node_cuts(G))
+    assert_true(len(solution) == len(cuts))
+    for cut in cuts:
+        assert_true(cut in solution)

pip install -e .
parse_log_pytest
requirements.txt
nose pytest
apt-get update apt-get install -y libgdal-dev graphviz
3.6
requirements/default.txt requirements/test.txt
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
attrs==22.2.0
certifi==2021.5.30
decorator==5.1.1
importlib-metadata==4.8.3
iniconfig==1.1.1
-e git+https://github.com/networkx/networkx.git@293632863d5e895691b56dff4b12c937b2ea77dc#egg=networkx
nose==1.3.7
packaging==21.3
pluggy==1.0.0
py==1.11.0
pyparsing==3.1.4
pytest==7.0.1
tomli==1.2.3
typing_extensions==4.1.1
zipp==3.6.0

name: networkx
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - certifi=2021.5.30=py36h06a4308_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.3=he6710b0_2
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=1.1.1w=h7f8727e_0
  - pip=21.2.2=py36h06a4308_0
  - python=3.6.13=h12debd9_1
  - readline=8.2=h5eee18b_0
  - setuptools=58.0.4=py36h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - wheel=0.37.1=pyhd3eb1b0_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - attrs==22.2.0
      - decorator==5.1.1
      - importlib-metadata==4.8.3
      - iniconfig==1.1.1
      - nose==1.3.7
      - packaging==21.3
      - pluggy==1.0.0
      - py==1.11.0
      - pyparsing==3.1.4
      - pytest==7.0.1
      - tomli==1.2.3
      - typing-extensions==4.1.1
      - zipp==3.6.0
prefix: /opt/conda/envs/networkx

networkx/algorithms/connectivity/tests/test_kcutsets.py::test_cycle_graph networkx/algorithms/connectivity/tests/test_kcutsets.py::test_complete_graph
networkx/algorithms/connectivity/tests/test_kcutsets.py::test_torrents_and_ferraro_graph networkx/algorithms/connectivity/tests/test_kcutsets.py::test_example_1 networkx/algorithms/connectivity/tests/test_kcutsets.py::test_random_gnp networkx/algorithms/connectivity/tests/test_kcutsets.py::test_shell networkx/algorithms/connectivity/tests/test_kcutsets.py::test_configuration networkx/algorithms/connectivity/tests/test_kcutsets.py::test_karate networkx/algorithms/connectivity/tests/test_kcutsets.py::test_articulation_points networkx/algorithms/connectivity/tests/test_kcutsets.py::test_grid_2d_graph networkx/algorithms/connectivity/tests/test_kcutsets.py::test_disconnected_graph networkx/algorithms/connectivity/tests/test_kcutsets.py::test_alternative_flow_functions networkx/algorithms/connectivity/tests/test_kcutsets.py::test_is_separating_set_complete_graph networkx/algorithms/connectivity/tests/test_kcutsets.py::test_is_separating_set networkx/algorithms/connectivity/tests/test_kcutsets.py::test_non_repeated_cuts
networkx/algorithms/connectivity/kcutsets.py
networkx/algorithms/connectivity/kcutsets.py