Since $d_1\in F_{ij}\ao{(t)}$, we have $d_1\in D(t)$ and therefore $t_{d_1}=t$. By the definition of $t_{d_1}$, this implies that there has been no communication between a node in $\{1,\ldots,d_1\}$ and a node in $\{d_1+1,\ldots,n\}$ during the time interval $[kB,t-1]$. It follows that $x_i(t) \geq
    y_{d_1}$. By a symmetrical argument, we also have $$x_j(t)\leq y_{d_k+1}.\label{cutbound}$$ These relations imply that $$x_i(t)-x_j(t) \geq y_{d_1}-y_{d_k+1}  \ao{\geq } \sum_{d\in F_{ij}\ao{(t)}} (y_d-y_{d+1}),$$ Since the components of $y$ are sorted in nonincreasing order, we have $y_d-y_{d+1}\geq 0$, for every $d\in F_{ij}\ao{(t)}$. For any nonnegative numbers $z_i$, we have $$(z_1+\cdots+z_k)^2\geq z_1^2+\cdots+z_k^2,$$ which implies that $$(x_i(t)-x_j(t))^2 \geq \sum_{d\in F_{ij}\ao{(t)}} (y_d-y_{d+1})^2.
    \label{eq:dx}$$

We now use these two observations to provide a lower bound on the expression on the right-hand side of Eq. (\[firstvdec0\]) at time $t$. We use Eq. (\[eq:dx\]) and then Eq. (\[eq:w\]), to obtain $$\begin{aligned}
\sum_{i<j} w_{ij}(t)(x_i(t)-x_j(t))^2&
\geq& \sum_{i<j} w_{ij}(t) \sum_{d\in F_{ij}\ao{(t)}} (y_d-y_{d+1})^2\\
&=&\sum_{d\in D(t)} \sum_{(i,j)\in C_d} w_{ij}(t) (y_d-y_{d+1})^2\\
&\geq& \frac{\eta}{2} \sum_{d\in D(t)}(y_d-y_{d+1})^2.\end{aligned}$$ We now sum both sides of the above inequality for different values of $t$, and use Eq. (\[firstvdec\]), to obtain $$\begin{aligned}
V(kB)-V((k+1)B)&=& \sum_{t=kB}^{(k+1)B-1} \sum_{i<j} w_{ij}(t)(x_i(t)-x_j(t))^2\\
&\geq&
\frac{\eta}{2} \sum_{t=kB}^{(k+1)B-1}\sum_{d\in D(t)}(y_d-y_{d+1})^2\\
&=&\frac{\eta}{2}\sum_{d=1}^{n-1} (y_d-y_{d+1})^2,\end{aligned}$$ where the last inequality follows from the fact that the union of the sets $D(t)$ 