Repository: networkx/networkx

Issue:
```is_k_edge_connected``` incorrectly returns True for k=2 with multi-component graphs without bridges
### Current Behavior

The implementation of ```is_k_edge_connected``` currently defers to ```is_connected``` for k=1, to ```has_bridges``` for k=2, and runs the full check for k>2.

As a result, this returns True for a multi-component graph without bridges.

### Expected Behavior

Since the graph has multiple components, it is not connected in the first place and ```is_k_edge_connected``` should return False for all (positive) values of k.

### Steps to Reproduce

```
import networkx as nx

G = nx.compose(nx.complete_graph([0, 1, 2]), nx.complete_graph([3, 4, 5]))
nx.connectivity.is_k_edge_connected(G, 2)
```

This returns True but should return False.

### Environment

Python version: 3.11.2
NetworkX version: 3.1

### Additional context

As defined in the NetworkX documentation, a bridge is an edge whose removal increases the number of connected components. It appears to me, then, that a graph not having bridges is a necessary-but-not-sufficient condition for a graph being 2-edge-connected.


Discussion:
dschult: I agree that in order to be 2-edge connected, the graph needs to be both connected and to have no bridges.

Can you add a test of a simple case to make sure we don't accidentally let this slip back in?

Thanks for this! 
kbvw: Sure!

Added a simple case of a two-component graph without bridges. This should not be k-edge-connected for k=2 or any k. Testing for (the graph not being k-edge-connected with) k in [1,2,3], as these are different dispatches in the implementation. The test graph has degree 3 everywhere to make sure it is not caught in the degree check and it actually gets dispatched up to k=3.

Hope that's fine!

Patch:
diff --git a/networkx/algorithms/clique.py b/networkx/algorithms/clique.py
index b725eabb4..7fd7e8166 100644
--- a/networkx/algorithms/clique.py
+++ b/networkx/algorithms/clique.py
@@ -18,11 +18,8 @@ __all__ = [
     "find_cliques_recursive",
     "make_max_clique_graph",
     "make_clique_bipartite",
-    "graph_clique_number",
-    "graph_number_of_cliques",
     "node_clique_number",
     "number_of_cliques",
-    "cliques_containing_node",
     "enumerate_all_cliques",
     "max_weight_clique",
 ]
@@ -511,106 +508,6 @@ def make_clique_bipartite(G, fpos=None, create_using=None, name=None):
     return B
 
 
-def graph_clique_number(G, cliques=None):
-    """Returns the clique number of the graph.
-
-    The *clique number* of a graph is the size of the largest clique in
-    the graph.
-
-    .. deprecated:: 3.0
-
-       graph_clique_number is deprecated in NetworkX 3.0 and will be removed
-       in v3.2. The graph clique number can be computed directly with::
-
-           max(len(c) for c in nx.find_cliques(G))
-
-
-    Parameters
-    ----------
-    G : NetworkX graph
-        An undirected graph.
-
-    cliques : list
-        A list of cliques, each of which is itself a list of nodes. If
-        not specified, the list of all cliques will be computed, as by
-        :func:`find_cliques`.
-
-    Returns
-    -------
-    int
-        The size of the largest clique in `G`.
-
-    Notes
-    -----
-    You should provide `cliques` if you have already computed the list
-    of maximal cliques, in order to avoid an exponential time search for
-    maximal cliques.
-
-    """
-    import warnings
-
-    warnings.warn(
-        (
-            "\n\ngraph_clique_number is deprecated and will be removed.\n"
-            "Use: ``max(len(c) for c in nx.find_cliques(G))`` instead."
-        ),
-        DeprecationWarning,
-        stacklevel=2,
-    )
-    if len(G.nodes) < 1:
-        return 0
-    if cliques is None:
-        cliques = find_cliques(G)
-    return max([len(c) for c in cliques] or [1])
-
-
-def graph_number_of_cliques(G, cliques=None):
-    """Returns the number of maximal cliques in the graph.
-
-    .. deprecated:: 3.0
-
-       graph_number_of_cliques is deprecated and will be removed in v3.2.
-       The number of maximal cliques can be computed directly with::
-
-           sum(1 for _ in nx.find_cliques(G))
-
-    Parameters
-    ----------
-    G : NetworkX graph
-        An undirected graph.
-
-    cliques : list
-        A list of cliques, each of which is itself a list of nodes. If
-        not specified, the list of all cliques will be computed, as by
-        :func:`find_cliques`.
-
-    Returns
-    -------
-    int
-        The number of maximal cliques in `G`.
-
-    Notes
-    -----
-    You should provide `cliques` if you have already computed the list
-    of maximal cliques, in order to avoid an exponential time search for
-    maximal cliques.
-
-    """
-    import warnings
-
-    warnings.warn(
-        (
-            "\n\ngraph_number_of_cliques is deprecated and will be removed.\n"
-            "Use: ``sum(1 for _ in nx.find_cliques(G))`` instead."
-        ),
-        DeprecationWarning,
-        stacklevel=2,
-    )
-    if cliques is None:
-        cliques = list(find_cliques(G))
-    return len(cliques)
-
-
 @nx._dispatch
 def node_clique_number(G, nodes=None, cliques=None, separate_nodes=False):
     """Returns the size of the largest maximal clique containing each given node.
@@ -678,29 +575,9 @@ def node_clique_number(G, nodes=None, cliques=None, separate_nodes=False):
 def number_of_cliques(G, nodes=None, cliques=None):
     """Returns the number of maximal cliques for each node.
 
-    .. deprecated:: 3.0
-
-       number_of_cliques is deprecated and will be removed in v3.2.
-       Use the result of `find_cliques` directly to compute the number of
-       cliques containing each node::
-
-           {n: sum(1 for c in nx.find_cliques(G) if n in c) for n in G}
-
     Returns a single or list depending on input nodes.
     Optional list of cliques can be input if already computed.
     """
-    import warnings
-
-    warnings.warn(
-        (
-            "\n\nnumber_of_cliques is deprecated and will be removed.\n"
-            "Use the result of find_cliques directly to compute the number\n"
-            "of cliques containing each node:\n\n"
-            "    {n: sum(1 for c in nx.find_cliques(G) if n in c) for n in G}\n\n"
-        ),
-        DeprecationWarning,
-        stacklevel=2,
-    )
     if cliques is None:
         cliques = list(find_cliques(G))
 
@@ -718,49 +595,6 @@ def number_of_cliques(G, nodes=None, cliques=None):
     return numcliq
 
 
-def cliques_containing_node(G, nodes=None, cliques=None):
-    """Returns a list of cliques containing the given node.
-
-    .. deprecated:: 3.0
-
-       cliques_containing_node is deprecated and will be removed in 3.2.
-       Use the result of `find_cliques` directly to compute the cliques that
-       contain each node::
-
-           {n: [c for c in nx.find_cliques(G) if n in c] for n in G}
-
-    Returns a single list or list of lists depending on input nodes.
-    Optional list of cliques can be input if already computed.
-    """
-    import warnings
-
-    warnings.warn(
-        (
-            "\n\ncliques_containing_node is deprecated and will be removed.\n"
-            "Use the result of find_cliques directly to compute maximal cliques\n"
-            "containing each node:\n\n"
-            "    {n: [c for c in nx.find_cliques(G) if n in c] for n in G}\n\n"
-        ),
-        DeprecationWarning,
-        stacklevel=2,
-    )
-    if cliques is None:
-        cliques = list(find_cliques(G))
-
-    if nodes is None:
-        nodes = list(G.nodes())  # none, get entire graph
-
-    if not isinstance(nodes, list):  # check for a list
-        v = nodes
-        # assume it is a single value
-        vcliques = [c for c in cliques if v in c]
-    else:
-        vcliques = {}
-        for v in nodes:
-            vcliques[v] = [c for c in cliques if v in c]
-    return vcliques
-
-
 class MaxWeightClique:
     """A class for the maximum weight clique algorithm.
 
diff --git a/networkx/algorithms/connectivity/edge_augmentation.py b/networkx/algorithms/connectivity/edge_augmentation.py
index ed9bd7c33..c1215509e 100644
--- a/networkx/algorithms/connectivity/edge_augmentation.py
+++ b/networkx/algorithms/connectivity/edge_augmentation.py
@@ -68,7 +68,7 @@ def is_k_edge_connected(G, k):
         if k == 1:
             return nx.is_connected(G)
         elif k == 2:
-            return not nx.has_bridges(G)
+            return nx.is_connected(G) and not nx.has_bridges(G)
         else:
             return nx.edge_connectivity(G, cutoff=k) >= k
 


Test patch:
diff --git a/networkx/algorithms/connectivity/tests/test_edge_augmentation.py b/networkx/algorithms/connectivity/tests/test_edge_augmentation.py
index 37ee29740..e1d92d996 100644
--- a/networkx/algorithms/connectivity/tests/test_edge_augmentation.py
+++ b/networkx/algorithms/connectivity/tests/test_edge_augmentation.py
@@ -75,6 +75,11 @@ def test_is_k_edge_connected():
     assert is_k_edge_connected(G, k=3)
     assert is_k_edge_connected(G, k=4)
 
+    G = nx.compose(nx.complete_graph([0, 1, 2]), nx.complete_graph([3, 4, 5]))
+    assert not is_k_edge_connected(G, k=1)
+    assert not is_k_edge_connected(G, k=2)
+    assert not is_k_edge_connected(G, k=3)
+
 
 def test_is_k_edge_connected_exceptions():
     pytest.raises(
diff --git a/networkx/algorithms/tests/test_clique.py b/networkx/algorithms/tests/test_clique.py
index 1bcbd4fe1..3bee21098 100644
--- a/networkx/algorithms/tests/test_clique.py
+++ b/networkx/algorithms/tests/test_clique.py
@@ -67,98 +67,66 @@ class TestCliques:
         with pytest.raises(ValueError):
             list(nx.find_cliques_recursive(self.G, [2, 6, 4, 1]))
 
-    def test_clique_number(self):
-        G = self.G
-        with pytest.deprecated_call():
-            assert nx.graph_clique_number(G) == 4
-        with pytest.deprecated_call():
-            assert nx.graph_clique_number(G, cliques=self.cl) == 4
-
-    def test_clique_number2(self):
-        G = nx.Graph()
-        G.add_nodes_from([1, 2, 3])
-        with pytest.deprecated_call():
-            assert nx.graph_clique_number(G) == 1
-
-    def test_clique_number3(self):
-        G = nx.Graph()
-        with pytest.deprecated_call():
-            assert nx.graph_clique_number(G) == 0
-
     def test_number_of_cliques(self):
         G = self.G
-        with pytest.deprecated_call():
-            assert nx.graph_number_of_cliques(G) == 5
-        with pytest.deprecated_call():
-            assert nx.graph_number_of_cliques(G, cliques=self.cl) == 5
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, 1) == 1
-        with pytest.deprecated_call():
-            assert list(nx.number_of_cliques(G, [1]).values()) == [1]
-        with pytest.deprecated_call():
-            assert list(nx.number_of_cliques(G, [1, 2]).values()) == [1, 2]
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, [1, 2]) == {1: 1, 2: 2}
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, 2) == 2
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G) == {
-                1: 1,
-                2: 2,
-                3: 1,
-                4: 2,
-                5: 1,
-                6: 2,
-                7: 1,
-                8: 1,
-                9: 1,
-                10: 1,
-                11: 1,
-            }
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, nodes=list(G)) == {
-                1: 1,
-                2: 2,
-                3: 1,
-                4: 2,
-                5: 1,
-                6: 2,
-                7: 1,
-                8: 1,
-                9: 1,
-                10: 1,
-                11: 1,
-            }
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, nodes=[2, 3, 4]) == {2: 2, 3: 1, 4: 2}
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, cliques=self.cl) == {
-                1: 1,
-                2: 2,
-                3: 1,
-                4: 2,
-                5: 1,
-                6: 2,
-                7: 1,
-                8: 1,
-                9: 1,
-                10: 1,
-                11: 1,
-            }
-        with pytest.deprecated_call():
-            assert nx.number_of_cliques(G, list(G), cliques=self.cl) == {
-                1: 1,
-                2: 2,
-                3: 1,
-                4: 2,
-                5: 1,
-                6: 2,
-                7: 1,
-                8: 1,
-                9: 1,
-                10: 1,
-                11: 1,
-            }
+        assert nx.number_of_cliques(G, 1) == 1
+        assert list(nx.number_of_cliques(G, [1]).values()) == [1]
+        assert list(nx.number_of_cliques(G, [1, 2]).values()) == [1, 2]
+        assert nx.number_of_cliques(G, [1, 2]) == {1: 1, 2: 2}
+        assert nx.number_of_cliques(G, 2) == 2
+        assert nx.number_of_cliques(G) == {
+            1: 1,
+            2: 2,
+            3: 1,
+            4: 2,
+            5: 1,
+            6: 2,
+            7: 1,
+            8: 1,
+            9: 1,
+            10: 1,
+            11: 1,
+        }
+        assert nx.number_of_cliques(G, nodes=list(G)) == {
+            1: 1,
+            2: 2,
+            3: 1,
+            4: 2,
+            5: 1,
+            6: 2,
+            7: 1,
+            8: 1,
+            9: 1,
+            10: 1,
+            11: 1,
+        }
+        assert nx.number_of_cliques(G, nodes=[2, 3, 4]) == {2: 2, 3: 1, 4: 2}
+        assert nx.number_of_cliques(G, cliques=self.cl) == {
+            1: 1,
+            2: 2,
+            3: 1,
+            4: 2,
+            5: 1,
+            6: 2,
+            7: 1,
+            8: 1,
+            9: 1,
+            10: 1,
+            11: 1,
+        }
+        assert nx.number_of_cliques(G, list(G), cliques=self.cl) == {
+            1: 1,
+            2: 2,
+            3: 1,
+            4: 2,
+            5: 1,
+            6: 2,
+            7: 1,
+            8: 1,
+            9: 1,
+            10: 1,
+            11: 1,
+        }
 
     def test_node_clique_number(self):
         G = self.G
@@ -196,34 +164,6 @@ class TestCliques:
         assert nx.node_clique_number(G, [1, 2], cliques=self.cl) == {1: 4, 2: 4}
         assert nx.node_clique_number(G, 1, cliques=self.cl) == 4
 
-    def test_cliques_containing_node(self):
-        G = self.G
-        with pytest.deprecated_call():
-            assert nx.cliques_containing_node(G, 1) == [[2, 6, 1, 3]]
-        with pytest.deprecated_call():
-            assert list(nx.cliques_containing_node(G, [1]).values()) == [[[2, 6, 1, 3]]]
-        with pytest.deprecated_call():
-            assert [
-                sorted(c) for c in list(nx.cliques_containing_node(G, [1, 2]).values())
-            ] == [[[2, 6, 1, 3]], [[2, 6, 1, 3], [2, 6, 4]]]
-        with pytest.deprecated_call():
-            result = nx.cliques_containing_node(G, [1, 2])
-        for k, v in result.items():
-            result[k] = sorted(v)
-        assert result == {1: [[2, 6, 1, 3]], 2: [[2, 6, 1, 3], [2, 6, 4]]}
-        with pytest.deprecated_call():
-            assert nx.cliques_containing_node(G, 1) == [[2, 6, 1, 3]]
-        expected = [{2, 6, 1, 3}, {2, 6, 4}]
-        with pytest.deprecated_call():
-            answer = [set(c) for c in nx.cliques_containing_node(G, 2)]
-        assert answer in (expected, list(reversed(expected)))
-
-        with pytest.deprecated_call():
-            answer = [set(c) for c in nx.cliques_containing_node(G, 2, cliques=self.cl)]
-        assert answer in (expected, list(reversed(expected)))
-        with pytest.deprecated_call():
-            assert len(nx.cliques_containing_node(G)) == 11
-
     def test_make_clique_bipartite(self):
         G = self.G
         B = nx.make_clique_bipartite(G)