Studying for my finals. I came across with the following statement:
Given two graphs $G_{1}=\left(V,E_{1}\right)$ and $G_{2}=\left(V,E_{2}\right)$, weight function $w\,:\,E_{1}\cup E_{2}\to\mathbb{R}$ and two minimal spanning trees $T_1$ and $T_2$ by $w$ of $G_1$ and $G_2$ respectively. Lets define $G=\left(V,E_{1}\cup E_{2}\right)$. Then there exists a MST $T$ of $G$ with $w$ so $T\subseteq T_{1}\cup T_{2}$.
This statement looks pretty obvious but the thing I'm struggling with is to write a "formal" proof. How to show this statement is true?
I do not think this is obvious at all. A quick proof that I see uses the following symmetric exchange lemma.
Lemma. Let $G = (V,E)$ be a connected graph and $T_1, T_2 \subseteq E$ two spanning trees. For every edge $e \in T_1$ there is an edge $f \in T_2$ such that both $T_1 - e + f$ and $T_2 - f + e$ are spanning trees.
Using the lemma, you can prove your statement as follows. Let $T$ be an MST of $G$ such that the intersection of $T$ with $T_1 \cup T_2$ is as large as possible. If $T \subseteq T_1 \cup T_2$ then we are done, so assume to the contrary that there is an edge $e \in T$ with $e \notin T_1 \cup T_2$. We may assume that $e \in E_1$. Since $T_1$ is a spanning tree of $G$, using the lemma we can find an edge $f \in T_1$ such that $T - e + f$ and $T_1 - f + e$ are both spanning trees of $G$. Note that $T_1 - f + e$ is also a spanning tree of $G_1$. Thus, since $T_1$ was an MST, we must have $w(f) \leq w(e)$. Then the weight of $T - e + f$ is at most the weight of $T$; since $T$ was an MST, this means that $T - e + f$ is an MST as well. But now $T - e + f$ has more edges in $T_1 \cup T_2$ than $T$, contradicting the choice of $T$.
The lemma is a special case of the symmetrix exchange property of matroid bases. But you can prove it directly without any knowledge of matroids. The basic observation that we need is that given a spanning tree $T$ and an edge $e \in E - T$, $T + e$ contains a unique circuit $C(T,e)$, called the fundamental circuit of $e$ with respect to $T$. Clearly, $e \in C(T,e)$, and furthermore for any $f \in T$, $T + e - f$ is a spanning tree if and only if $f \in C(T,e)$.
Now in the lemma we can assume that $e \notin T_2$, since otherwise we can take $f = e$. By the preceding discussion what we need to show is that there is some $f \in C(T_2,e)$ such that $e \in C(T_1,f)$. Let $u,v$ be the endpoints of $e$ and let $u = v_1, \ldots, v_k = v$ be the vertices of the unique path in $T_2$ between $u$ and $v$. Finally, let $P_{i}$ be the unique path in $T_1$ between $v_i$ and $v_{i+1}$. After decoding all the notation, it should be clear that $C(T_1,v_iv_{i+1})$ is just $P_i + v_iv_{i+1}$. Since concatenating the walks $P_1,\ldots,P_{k-1}$ gives a $u-v$ walk in $T_1$, there must be an index $i$ such that $uv$ is an edge of $P_i$. But this means exactly that for $f = v_iv_{i+1}$, we have $e \in C(T_1,f)$.