referred to as a communication across the cut $d$.

-   For all $t\in \{kB,\ldots,(k+1)B-1\}$, let $D(t)=\{d\mid
    t_d=t\}$, i.e., $D(t)$ consists of “cuts" $d\in \{1,\ldots,n-1\}$ such that time $t$ is the first communication time larger than or equal to $kB$ between nodes in the sets $\{1,\ldots,d\}$ and $\{d+1,\ldots,n\}$. Because of Assumption \[weakconnect\], the union of the sets $D(t)$ includes all indices $1,\ldots,n-1$, except possibly for indices for which $x_d(kB)=x_{d+1}(kB)$.

-   For all $d\in \{1,\ldots,n-1\}$, let $C_d=\{(i,j) \alexo{,~(j,i)}  \mid i\leq d, \ d+1\leq j\}$.

-   For all $t\in \{kB,\ldots,(k+1)B-1\}$, let $F_{ij}(t) =\{d\in D(t)\
    |\ (i,j) \alexo{\mbox{ or } (j,i)} \in C_d\}$, i.e., $F_{ij}(t)$ consists of all cuts $d$ such that the edge $(i,j)$ at time $t$ is the first communication across the cut at a time larger than or equal to $kB$.

-   To simplify notation, let $y_i=x_i(kB)$. By assumption, we have $y_1\geq\cdots\geq y_n$.

We make two observations, as follows:

-   Suppose that $d\in D(t)$. Then, for some $(i,j)\in C_d$, we have either $a_{ij}(t)>0$ or $a_{ji}(t)>0$. by Lemma \[db\], we obtain $$\sum_{(i,j)\in C_d} w_{ij}(t)\geq \frac{\eta}{2}. \label{eq:w}$$

-   Fix some $(i,j)$, with $i<j$, and time $t\in
    \{kB,\ldots,(k+1)B-1\}$, and suppose that $F_{ij}(t)$ is nonempty. Let $F_{ij}\ao{(t)}=\{d_1,\ldots,d_k\}$, where the $d_j$ are arranged in increasing order. 