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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .