The average connectivity of a graph (Q1613484)

For a graph \(G=(V,E)\) with \(u,v\in V\), let \(\kappa_G(u,v)\) denote the maximum number of internally disjoint \(uv\)-paths in \(G\). Thus \(\kappa(G):=\min\{\kappa_G(u,v):u,v\in V\}\). Define average connectivity of \(G\) to be \[ \overline{\kappa}(G)=\sum_{u,v\in V}\kappa_G(u,v)\Biggl/{|V|\choose 2}; \] it is computable in polynomial time. Upper bounds for \(\overline{\kappa}(G)\) are given in terms of the independence number, the degree sequence, and \(|V|\) and \(|E|\), respectively, this last bound being sharp. Theorem 3.1: If \(\overline{\kappa}(G)=\kappa(G)=k\), then \(k\geq 1\) implies \(\kappa(G-e)<k\) for all \(e\in E\), and \(k\geq 2\) implies \(\kappa(G-v)<k\) for all \(v\in V\). Three methods are given for constructing graphs satisfying the hypothesis of this theorem.