# simple lower bound for constructing a Spanning tree

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|$

• What have you tried? Where did you get stuck? What specifically is your question? Can you identify a more narrowly scoped question about your attempt and what you need help with? – D.W. Nov 28 '14 at 9:27

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$ be the 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 execution of $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.

• For future reference: We're looking for answers that you are confident in (not guesses, not attempts that you want feedback on). Not sure whether that applies in this case or not, but I just wanted to let you know so that you can be aware of the expectations on this site. – D.W. Nov 28 '14 at 9:28
• This is not an attempt. My teacher tells me that my answer is correct. – Duccio Bertieri Dec 2 '14 at 21:35
• When you write "I tried to solve this problem...", it sounds like you are not confident whether your answer is correct. – D.W. Dec 3 '14 at 4:28