Connectivity Parameters

Given an un-directed graph $G = \langle V, E \rangle$ without self loops and duplicates,

Connectivity. The connectivity of an edge $e = (u, v)$, denoted as $\lambda_e$, is the minimum number of edges to remove to disconnect $u$ from $v$.

Strength. The strength of an edge $e = (u, v)$, denoted as $s_e$, is the maximum positive integer $k$, s.t., it belongs to a $k$-connected vertex induced sub-graph. A sub-graph is called $k$-connected if its min-cut is at least $k$.

Theorem

1. $\sum_{e \in E} 1 / s_e \le n - 1$, where $n = |V|$.
2. $\sum_{e \in E} 1 / \lambda_e \le n - 1$

Proof. We prove claim 1 by induction on the number of vertices $n$. When $n = 2$, $|E| = 1$, the strength of the only edge is $1$. Therefore $\sum_{e \in E} 1 / s_e = 1 / 1 = 1$. Suppose claim 1 holds for all graphs with $n - 1$ vertices. For a graph with $n$ vertices, consider a particular min-cut $(S, \bar{S}) \in V \times V$. If an edge $e = (u, v)$ is in the min-cut, then its strength is at most $\lambda = G(S, \bar{S})$ (the min-cut value), since we need to remove at most $\lambda$ edges to disconnect $u$ from $v$ in arbitrary vertex induced sub-graph that contains $e$. But the original graph $G$ contains $e$ and has connectivity $\lambda$. It follows that the strength of $e$ is $\lambda$ and

Finally, similar argument applies to claim 2.