Given two weighted, undirected graphs on $$$n$$$ nodes $$$G_1$$$ and $$$G_2$$$, is it possible to efficiently find a tree on these $$$n$$$ nodes that is an MST of both $$$G_1$$$ and $$$G_2$$$?

UPD: Building on chromate00's comments, it turns out that we can simply construct a new graph $$$G$$$ where the weight of each edge is the sum of that edge's weights in $$$G_1$$$ and $$$G_2$$$, and find the MST on this graph (in chromate00's notation here, this means we can actually just always set $$$C = 1$$$). If a common MST exists, we can guarantee that this algorithm will always find it.

Proof. Let $$$W_1$$$, $$$W_2$$$, and $$$W$$$ denote the total weight of MSTs for $$$G_1$$$, $$$G_2$$$, and $$$G$$$ respectively.

• Note that $$$W_1 + W_2 \leq W$$$.
• Also note that the weight of any spanning tree in $$$G_1$$$ is at least $$$W_1$$$, and similarly for $$$G_2$$$. Therefore, if we find a spanning tree $$$T$$$ with exactly $$$W = W_1 + W_2$$$, it must follow that $$$T$$$ has exactly weight $$$W_1$$$ in $$$G_1$$$ and exactly weight $$$W_2$$$ in $$$G_2$$$, since these are the minimum possible.

Here's a problem that uses this idea: 1054G - New Road Network

(This writeup is also available on my personal blog!)