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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.