Number of messages per node in a fully connected graph I have a fully connected graph $G$. Each node in the graph sends 1 message per second to another randomly selected node. The message is not forwarded directly to the destination node, but instead, the sender node selects 3 random intermediate nodes through which the message should go before reaching the destination (e.g, if node A wants to send a message to node B, A selects three intermediate nodes $X_1, X_2, X_3$ and sends the message as A->$X_1$->$X_2$->$X_3$->B). How can I calculate what is the average throughput of a single node, i.e., how many messages per second a single node receives?
 A: Think about the starting node for each message actually sending $4$ small messages, each of which are received by a separate node (intermediate or end). Thus, if the number of nodes is equal to $n$, there are $4n$ small messages sent per second. However, since each sent message is received, the rate at which messages are received must be the rate at which messages are sent. Thus, there are also $4n$ small messages received per second on average, so the number per node is $\frac{4n}{n} = \boxed{4\text{ messages per second.}}$
Another argument:
Note that the probability of any given node receiving a message sent by another given node is $\frac{4}{n-1}$, because the sending node must choose $4$ out of the $n-1$ remaining nodes to route its message through. Then, since the rate of messages received is the same as the rate sent, namely $1$ per second, the node gets an expected value of $\frac{4}{n-1}$ messages per second from the other given node. Multiplying this by the $n-1$ possible sending nodes, the node receives $(n-1)\frac{4}{n-1} = \boxed{4\text{ messages per second.}}$
