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

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$$.

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 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).$$

• Interesting! It looks like this would generalize to arbitrary $k$ if we could be certain of finding a $k$-fold multiple edge in the multigraph. But your $k=2$ proof uses the simple graph case, and we can't copy that part immediately, because for $k>2$ you can have edges with multiplicity between $2$ and $k-1$... Sep 4, 2019 at 16:04
• I will give you the bounty because solving the $k=2$ case is nice, but I am still hoping for a general-$k$ answer one of these days... Sep 4, 2019 at 16:05

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.