i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts the algorithm} the problems of constructing a spanning tree takes at least $\Omega(m)$ messages, where $m=|E|$
simple lower bound for constructing a Spanning tree
distributed systems;lower bounds;spanning trees
i tried to solve this problem in this way:Assume that there exists a correct SPT protocol $A$ thatuses fewer than $m$ messages. This means that there is at least one link in $G$ where no message is transmitted.Consider an execution of the algorithm on $G$, and let $e = (x, y) \in E$ bethe link where no message is transmitted by $A$.Now construct a new graph $G^{'}$  from $G$by removing the edge $e$ and adding a new node $z$ and two new edges $e1 = (x, z)$ and$e2 = (y, z)$. Set $z$ in a noninitiator status ($z$ does not starts the execution of the algorithm). Run exactly the same executionof $A$ on the new graph $G$   : since no message was sent along $(x,y)$ in the original execution in $G$, $x$ and $y$ never send a message to $z$ in the current execution in $G^{'}$   ; and since $z$ is not an initiator and does not receive any message, it will not send any message. At the end of the alghoritm a tree $T$ should have been constructed,however, $z$ is not part of $T$, and hence $T$ does not span $G$.in other words $A$ works only if $z$  is in a initiator status, therefore $A$ is not correct.