Connectivity of a Graph

Suppose the edge connectivity of a graph $G$ is $c$ . In the previous article we know that the number of cuts with weight up to $kc$ is bounded by $O((2n)^{2k})$ , where $k$ is a real number and $n$ is the number of vertices in $G$ .

Let $f(x)$ to be the number of cut with value $xc$ and define $F(k) = \Sigma_{x \le k} f(x)$ . From the discussion above, $F(k) \le \lambda (2n)^{2k}$ for some constant $\lambda$ .

If we remove each edge with probability $p$ , then the graph becomes disconnected with probability at most

\Pr[\text{Disconnected}] = \Sigma_{x} f(x)p^{xc}.

To maximize $\Pr[\text{Disconnected}]$ , we take $F(k) = \lambda (2n)^{2k}$ for every $k$ .

By the definition of $F(k)$ , $f(k) = \lambda ((2n)^{2k} - (2n)^{2(k-1)})$ .

Then, for $k \ge 2$ ,

\begin{aligned} f(k) p^{kc} &= \lambda ((2n)^{2k} - (2n)^{2(k-1)}) p^{kc} \\ &= \lambda \left( \int_{k -1}^{k} {\partial (2n)^{2x} \over \partial x} dx \right) \cdot p^{kc} \\ &\le \lambda \int_{k -1}^{k} {\partial(2n)^{2x} \over \partial x} p^{xc}dx \end{aligned}

Sum up this inequality over $k$ ,

\begin{aligned} \Pr[\text{Disconnected}] &\le f(1)p^c + \lambda \int_1^\infty {\partial (2n)^{2x} \over \partial x} p^{xc} dx \\ & = \lambda (2n)^2 p^c - \lambda {2\ln 2n \over 2 \ln 2n + c \ln p} (2n)^2 p^c \end{aligned}

If $p = (2n)^{-{a \over c} }$ for some parameter $a$ , then $\Pr[\text{Disconnected}] = O(n^2 p^c / (a - 2)) = O(n^{2 - a} / (a -2))$ . When $a = 3$ , the graph is disconnected with probability $O(1/n)$ . (p.s: for large $c$ , $p \approx 1 - {a \ln 2n \over c}$ )