Maximum number of edges in minimally $k$-edge-connected multigraph

Question

A graph or multigraph is $k$-edge-connected if it cannot be disconnected by deleting fewer than $k$ edges. It is minimally $k$-edge-connected if it loses this property when any edges are deleted. (Equivalently, if any edge of the graph is part of a $k$-edge cut).

According to this paper,

It is easy to show that a minimally $k$-edge-connected multigraph on $n$ vertices has at most $k(n-1)$ edges, and that this value is best possible for all values of $n$ and $k$.

I can see how this is best possible: if you take any $n$-vertex tree, and replace each edge of the tree by $k$ parallel edges, then we get a minimally $k$-edge-connected graph.

(To disconnect it, we need to destroy an entire edge of the original tree, which requires deleting $k$ edges. Every edge is part of such a $k$-edge cut, together with its parallel copies.)

How do we show this?

Notes:

• This came up in my answer to this question, where I gave a proof that for simple graphs, the maximum number of edges is smaller.
• A possibly-useful lemma (see this question) is that any minimally $k$-edge-connected graph, or multigraph, has a vertex of degree exactly $k$.

Answer 1

We induct on $k$; for $k=1$, this statement is just the claim that every minimally connected $n$-vertex graph is a tree (with $n-1$ edges).

Now let's take a minimally $k$-edge-connected $n$-vertex graph $G$. Inside it, let $H$ be any minimally $(k-1)$-edge-connected spanning subgraph, and let $F$ be the subgraph consisting of all edges of $G$ not in $H$. By induction, $H$ has at most $(k-1)(n-1)$ edges, and if $F$ has at most $n-1$ edges, we're done.

To prove this, we prove that $F$ is a forest. Let $e$ be any edge of $F$; by the minimality of $G$, it is part of a $k$-edge cut. In other words, there is a partition $V(G) = S \cup T$ such that $G$ has only $k$ edges between $S$ and $T$, and one of them is $e$. Well, because $H$ is $(k-1)$-edge-connected, $H$ has at least $k-1$ edges between $S$ and $T$. That and $e$ already gets us up to $k$ edges. Therefore $F$ can have no other edges between $S$ and $T$.

This proves that $e$ is a bridge of $F$, so it is not part of any cycle in $F$. Because $e$ was arbitrary, we conclude that no edges of $F$ are part of any cycles in $F$: $F$ is a forest. Therefore $|E(F)| \le n-1$, and $|E(G)| = |E(H)| + |E(F)| \le k(n-1)$, as desired.

Answer 2

For $k=1$, minimally $k$-edge-connected multigraphs on $n$ vertices are exactly trees, for which the required bound holds.

We can prove the required claim also for $k=2$ by induction with respect to $n$ as follows. The claim states that for $n=1$ the considered multigraph has no edges and for $n=2$ the considered multigraph has at most two edges; both these statements are true. Assume that the claim is already proved for all numbers from $1$ to $n\ge 2$. Let $G$ be any minimally $2$-edge-connected multigraphs with $n+1$ vertices and $m$ edges. Clearly, $G$ has no loops. If the multigraph $G$ has no multiple edges then it is a graph and by Theorem from your answer, it has at most $2n-3\le 2(n-1)$ edges.

Assume that $G$ has an edge $e$ of multiplicity $l\ge 2$. By the minimality of $G$, it has an edge $e'$ such that a multigraph $G'$, which is $G$ without edges $e$ and $e'$, is disconnected. If $e'$ is not a copy of $e$ then $G$ without $e'$ is disconnected too, which contradicts the minimality of $G$. So $e'$ is a copy of $e$ and $l=2$. By this answer, the multigraph $G'$ has exactly two connected components, which we denote by $G_1$ and $G_2$. It is easy to see that endpoints of $e$ belong to distinct connected components of $G'$, so both submultigraphs $G_i$ are induced,

We claim that each $G_i$ is a minimally $2$-edge-connected multigraph.

Indeed, suppose to the contrary that there exists an edge $e''$ of $G_i$ such that a multigraph $G_i- e''$ is disconnected. It is easy to see that endpoints $v$ and $u$ of $e''$ belong to distinct connected components of $G_i$. Since the multigraph $G-e''$ is connected, there exists a shortest path $P$ in $G-e''$ from $v$ to $u$. If $P$ has a vertex of $G_{3-i}$ then going from $G_i$ to $G_{3-i}$, $P$ has to cross $e$ and its copy $e'$, and also $P$ should cross them going back from $G_{3-i}$ to $G_i$, but in this case $P$ can be shortened, a contradiction. If $P$ has no vertices of $G_{3-i}$ then all vertices of $P$ belong to $G_i$, so $P$ connects $v$ and $u$ in $G_i- e''$, a contradiction.

Now suppose to the contrary that there exists an edge $e''$ of $G_i$ such that a multigraph $G_i- e''$ is 2-edge-connected. Since the multigraph $G_i- e''$ is not 2-edge-connected, there exists an edge $e'''$ of $G$ such that a multigraph $G''$, which is $G$ without edges $e''$ and $e'''$, is disconnected. It is easy to see that endpoints $v$ and $u$ of $e''$ belong to distinct connected components of $G''$. Since the multigraph $G-e''$ is connected, there exists a shortest path $P$ in $G-e''$ from $v$ to $u$. If $P$ has a vertex of $G_{3-i}$ then going from $G_i$ to $G_{3-i}$, $P$ has to cross $e$ and its copy $e'$, and also $P$ should cross them going back from $G_{3-i}$ to $G_i$, but in this case $P$ can be shortened, a contradiction. So $P$ has no vertices of $G_{3-i}$ and its vertices belong to $G_i$. Since $P$ crosses $e'''$, and the submultigraph $G_i$ is induced, $e'''$ also belongs to $G_i$. But then a multigraph $G_i$ without edges $e''$ and $e'''$ is disconnected, being a submultigraph of a disconnected multigraph $G''$, containing vertices from its different components, a contradiction with 2-edge-connectivity of the multigraph $G_i- e''$.

For each $i=1,2$ let $n_i<n$ be the number of vertices of $G_i$ and $m_i$ edges. Clearly, $n_1+n_2=n$ and $m_1+m_2=m-2$. By the inductive hypothesis, $m_i\le 2(n_i-1)$ for each $i$. Thus $$m=m_1+m_2+2\le 2(n_1-1)+ 2(n_2-1)+2=2(n_1+n_2-1)=2(n-1).$$