Sea K_n sea su parte totalmente conexa con conjunto de vértices v_1,\ldots,v_n . Sea P=(w_c,w_{c-1},\ldots,w_1) sea tu cola donde w_1 está conectado a v_1 por una sola arista.
Denote la distancia entre vértices a y b por d(a,b) .
Caso 1 : a=v_i y b=v_j para algunos i\neq j . Entonces d(v_i,v_j)=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}}.