Suppose I have $n$ complete graphs with $m$ nodes each. How many edges between graphs do I need to create so that there is a path of length 2 between any two nodes?
I am pretty sure that the answer is $(n-1)m$ by constructing a star graph with one central edge connected to all nodes, while all the other nodes are just connected within each complete graph. However, I can't prove that this is the minimal number.
Your answer is correct. Each subgraph $g_i$ is equivalent to every other subgraph, and every vertex in the set of graphs is equivalent (under permutation relabling) to every other vertex. Thus we can arbitrarily pick one, call it $v \in g_1$. To have a path of length $2$ between each vertex in $g_1$ to every other vertex in all other subgraphs requires $(n-1)m$ edges.