I try to provide a strict and mathematical rigorous proof to the following problem in Distributed Algorithms.
Prove or make a contradiction: if to vertices $a$ and $b$ on the network $G$ are located on the distance $k$ from each other, and there are $k^2$ different paths on different edges, so it is possible to transfer $k^2$ messages from $a$ to $b$ in time $\text{O}(k)$.
In my opinion. it's not true, I will try to show why. Let's say we have a network as on the picture with vertices $a$ and $b$, all vertices are different and there are 3 paths. The distance from $a$ to $b$ is $k$, in the case of synchronous communication, on every $k/2$ vertices the is collision of $k^2$ messages (the number of paths). In general, it's possible to build a network (not like on the picture), where the worst case occurs (first outgoing messages goes on the longest path and last outgoing message on the shortest path, finally they will make collision again).
Finally, we will get, $\sum_{0}^{\frac{k}{2}} k^2$ - collisions, which is greater than $\text{O}(k)$.
Does it make sense? Is it enough rigorous?
