Number of edges in a minimal $k$-edge connected subgraph We know that any minimal connected subgraph of a connected graph with $n$ nodes has exactly $n-1$ edges.
What are the known bounds (especially upper bounds) for the number of edges in a minimal $k$-edge connected subgraph? 
I assume that there are at most $O(kn)$ edges in a minimal solution, but I haven't managed to find results on this matter. 
 A: A theorem of Mader, proved (in German) in this paper, says that in any edge-minimal, $k$-edge-connected graph on $n \ge 3k-2$ vertices, there are at most $k(n-k)$ edges. This is tight for the complete bipartite graph $K_{k,n-k}$.
As a corollary, every $k$-edge-connected graph has a spanning $k$-edge-connected subgraph with at most $k(n-k)$ edges. As long as the graph has more edges than this, it is not minimal and therefore we can delete an edge from it and keep it $k$-edge-connected. Once we're done deleting all these edges, we get the spanning subgraph we wanted.
The proof in Mader's paper is a couple pages long altogether, and hard to read not so much because it's in German as because it uses German graph theory notation from 1971. In particular, it uses $\kappa(G)$ not for the connectivity of $G$ but for the number of edges in $G$, which sure tripped me up when I started reading. I don't want to translate the whole thing, but here is a proof of a slightly weaker version, also from this paper:
Theorem. Let $G$ be a $k$-minimal (edge-minimal, $k$-edge-connected) graph with $|G|\ge k+1$ vertices. Then its number of edges $\|G\|$ satisfies $$\|G\| \le k|G|-\binom{k+1}{2}.$$
Proof. If this is false, we can let $H$ be a subgraph of $G$ with the fewest vertices, satisfying $|H|\ge k+1$ and $\|H\| > k|H| - \binom{k+1}2$. Actually, we must have $|H|>k+1$, since even a complete $k+1$-vertex graph cannot strictly satisfy the second inequality. By our choice of $H$, for all $v \in V(H)$, $H-v$ must fail the second inequality, which means $\deg_H(v) \ge k+1$ for all $v \in V(H)$. 
We show that $H$ is $(k+1)$-edge-connected. Suppose not; let $S$ be an edge cut of $H$ with $|S| \le k$, so that $H-S$ has two components $H_1$ and $H_2$. The sum of $H$-degrees of vertices in $H_1$ is at least $(k+1)|H_1|$, and at most $k$ of these come from edges in $S$, so $\|H_1\| \ge \frac{(k+1)|H_1|-k}{2}$; from $\|H_1\| \le \binom{|H_1|}{2}$, this is only possible if $|H_1| \ge k+1$. Similarly, $|H_2| \ge k+1$. Since we could not have chosen either $H_1$ or $H_2$ in place of $H$, we must have $\|H_i\| \le k|H_i| - \binom{k+1}2$ for $i=1, 2$. Therefore $\|H\| \le \|H_1\| + \|H_2\| + k$ leads to $\|H\| \le k|H| - \binom{k+1}2$, contradicting the inequality by which we chose $H$.
Therefore $H$ is $(k+1)$-edge-connected. Let $vw \in E(H)$; by $(k+1)$-edge-connectivity, there are $k+1$ edge-disjoint $v,w$-paths in $H$: $k$ of them, not counting the edge $vw$ itself. These also exist in $G$.
But now, we can show that $G-vw$ is still $k$-edge-connected, contradicting $G$'s $k$-minimality. Remove any $k-1$ edges from $G-vw$, and one of the edge-disjoint paths we found still survives, so $v$ and $w$ are in the same component of the result. So the $k-1$ edges we removed cannot disconnect $G-vw$, or else they would disconnect $G$.

It's mentioned in a different paper that it is "easy to show" an upper bound of $k(n-1)$, and that this is true even for multigraphs. (It's tight for multigraphs: just take any tree, and replace each edge by $k$ copies of that edge.) But I sure don't see how it's easy to show this.
