1
$\begingroup$

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$.
$\endgroup$
1
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$... $\endgroup$ – Misha Lavrov Sep 4 at 16:04
  • 1
    $\begingroup$ 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... $\endgroup$ – Misha Lavrov Sep 4 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.