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