Messages in a graph structure

Hello

Suppose we have a graph, with unknown number of nodes and edges. It is required to implement a simple broadcast algorithm, where

-One node, as the initiator, sends one message to its neighbors.

-Each neighbour, sends the message received to its neighbors, but not the node it initially got it from

- If a node receives two messages, it will only forward the first copy to its neighbors, and ignore the 2nd message.

I am trying to find an exact formula for

Number of messages exchanged = function of number of nodes and edges.

#### Note: I have heard that the no of msg might be equal to (2*Edges) - n + 1. Not sure if this is right, still trying to figure out a way to prove it.... If you think it is right, please let me know how to prove it ....

Could someone help me please?

Many Thanks

Re: Messages in a graph structure

A related question which might help me find the answer .... Does anyone know how to compute the exact number of steps required to traverse a tree in BFS or DFS? Is it 2(nodes-1)?

Thanks