Sea Kn sea su parte totalmente conexa con conjunto de vértices v1,…,vn . Sea P=(wc,wc−1,…,w1) sea tu cola donde w1 está conectado a v1 por una sola arista.
Denote la distancia entre vértices a y b por d(a,b) .
Caso 1 : a=vi y b=vj para algunos i≠j . Entonces d(vi,vj)=1 así que \sum_{i,j,i\neq j} d(v_i,v_j) =\sum_{i,j,i\neq j} 1 ={n\choose 2}.
Caso 2 : a=w_i y b=v_1 : Entonces d(a,b)=i así que \sum_{i=1}^c d(w_i,v_1) = 1+2+\cdots c = {c+1\choose 2}.
Caso 3 : a=w_i y b=v_j para j\neq 1 . Entonces d(a,b)=i+1 . Así \sum_{j=2}^n\sum_{i=1}^c d(w_i,v_j) = \sum_{j=2}^n\sum_{i=1}^c i+1 = (n-1)\left({c+1\choose 2}+c\right).
Caso 4 : a=w_i y b=w_j para algunos i<j . Entonces d(a,b)=j-i . Así que \sum_{j=1}^c\sum_{i=1}^{j-1} d(w_j,w_i) = \sum_{j=1}^c\sum_{i=1}^{j-1} j-i = {c+1\choose 3}.
Si lo juntamos todo, vemos que la distancia media es de
\frac{{n\choose 2}+n{c+1\choose 2}+c(n-1)+{c+1\choose 3}}{{n+c\choose 2}}.