If you can only send messages in $G$, then you can simulate sending messages in $G^2$ as follows. Say that $u$ has a neighbor $w$ in $G^2$; this means $u$ and $w$ have a common neighbor in $G$. Then $u$ sends a message to $v$ with the contents "Pass the following on to $w$: ..." This requires a total of two messages to be sent.
So the specific claim we're proving is this. Suppose we have a function $f(G)$ that we want to compute, and a distributed algorithm living on a network the shape of $G$ can compute $f(G)$ in $T(G)$ steps. In that case:
- A network that actually has the shape of $G^2$ can compute $f(G^2)$ in $T(G^2)$ steps.
- A network that only has the shape of $G$ but simulates sending messages in $G^2$ can still compute $f(G^2)$, but it will take $2T(G^2)$ steps.
Some caveats, which your model of computation might or might not care about:
- This reduction only works if $u$ knows that $w$ is its neighbor in $G^2$, and that $w$ can be reached via $v$. We can achieve this by a discovery phase at the beginning: assuming that each vertex starts out with a knowledge of the IDs of all its neighbors, each vertex sends every neighbor a message saying "Here are the IDs of all my neighbors." This adds some unavoidable term to the total time.
- In distributed computation, the total number of messages sent might not be the most important parameter to track: maybe we should track the maximum number of messages each vertex has to deal with? Unfortunately, this can increase by more than a factor of $2$. Suppose that $G$ is a star graph: one central vertex $v$ with $n-1$ neighbors. Then $G^2$ is a complete graph. If an algorithm requires each vertex to send a message to each neighbor, then in $G^2$ no vertex needs more than $n-1$ messages. However, when $G$ is simulating $G^2$, the central vertex will also have to forward $(n-1)(n-2)$ messages, which is a quadratic increase.