# Maximum set of edges or vertices that doesn't disconnect graph

A graph is k-connected if every set of fewer than k vertices does not disconnect the graph, and a graph is k-edge-connected if every set of fewer than k edges does not disconnect the graph. The connectivity of a graph is the largest k for which it is k-connected, and the edge-connectivity of a graph is the largest k for which it is k-edge-connected.

I'm interested in the related concept of the largest k for which some set of k edges in a connected graph does not disconnect the graph (though other sets of k or fewer edges might disconnect the graph). In a cursory internet search, I couldn't find anything on this (or the related concept for vertices), so I'm asking here whether this has already been studied and given a name (or several names by different people who studied it independently)? If so, what is it called, and what is known about how to characterize graphs with a non-disconnecting set of k edges, how to find the largest size of a non-disconnecting set of edges, or how to find an actual non-disconnecting set of edges of maximum size?

If a graph G has a Hamiltonian path, then the largest non-disconnecting set has $$|E(G)| - |V(G)| + 1$$ edges (namely, for any Hamiltonian path of G, all edges except those on the Hamiltonian path). For a tree T there are no non-disconnecting sets of edges. But what about graphs that are not trees and have no Hamiltonian paths?

Note that the corresponding concept for vertices would have to be a set of vertices such that neither it nor any of its subsets disconnects the graph, as otherwise every set of $$|V(G)| - 1$$ vertices would be a maximum size non-disconnecting set.

As an example of the difference between these concepts and k-connectivity and k-edge-connectivity, the complete graph on n vertices $$K_n$$ is n-connected and n-edge-connected. If the vertices are labeled $$v_0$$ to $$v_{n-1}$$, consider the graph obtained by subdividing the edge $$\{v_0,v_1\}$$, replacing it with two edges $$\{v_0,u\}$$ and $$\{u,v_1\}$$. This new graph is 2-connected and 2-edge-connected, as deleting the two vertices $$v_0$$ and $$v_1$$ leaves $$u$$ as an isolated vertex, as does deleting the two edges $$\{v_0,u\}$$ and $$\{u,v_1\}$$. However, the set of n-1 vertices $$v_1$$ to $$v_{n-1}$$ is one whose deletion doesn't disconnect the graph, nor does the deletion of any of its subsets. Similarly, the set of edges containing all $$\{v_i,v_j\}$$ for which $$i+1 \lt j$$ is a set of $${n-1 \choose 2}$$ edges that disconnects neither $$K_n$$ nor the new graph.

This issue arose when I was looking at classes of graphs that have the same degree sequences and the same edge-degrees sequences (not a standard terminology, but I'm using it to mean pairs of degrees of the edges' incident vertices). I wanted to set a canonical representation of a class as one with the fewest number of components, and I found that if I started with an arbitrary graph of a class I could reduce the number of its components without changing the degree or edge-degrees sequences by replacing $$\{v_0,v_1\}$$ in one component and $$\{u_0,u_1\}$$ in another component, where $$deg(v_0) = deg(u_0)$$ and $$deg(v_1) = deg(u_1)$$, with $$\{v_0,u_1\}$$ and $$\{u_0,v_1\}$$. This only actually reduces the number of components if at least one of the old edges being replaced is not a bridge in its component. So, in the case where a bunch of the components are trees, I wanted to know how many tree components the non-tree component could absorb.

Immediately after posting the question, I realized that the answer is simple enough that maybe no one bothered to give the concept a name (at least in the edges case that prompted me to ask it). If a graph G is connected, it has a spanning tree, which has $$|V(G)| - 1$$ edges just as a Hamiltonian path would, and the edges of G other than in the spanning tree would be a set of maximum size $$|E(G)| - |V(G)| + 1$$ whose deletion doesn't disconnect G. Thus the number is easy to find, and the algorithms for finding a set are basically those for finding a spanning tree.