Question

Suppose that \({{\bf{T}}_{\bf{1}}}\)and \({{\bf{T}}_{\bf{2}}}\) are spanning trees of a simplegraph G. Moreover, suppose that \({{\bf{e}}_{\bf{1}}}\) is an edge in \({{\bf{T}}_{\bf{1}}}\)that is not in\({{\bf{T}}_{\bf{2}}}\). Show that there is an edge \({{\bf{e}}_{\bf{2}}}\)in \({{\bf{T}}_{\bf{2}}}\)that is not in \({{\bf{T}}_{\bf{1}}}\)such that\({{\bf{T}}_{\bf{1}}}\) remains a spanning tree if \({{\bf{e}}_{\bf{1}}}\)is removed from it and \({{\bf{e}}_{\bf{2}}}\) is added to it, and \({{\bf{T}}_{\bf{2}}}\)remains a spanning tree if \({{\bf{e}}_{\bf{2}}}\) is removed from it and \({{\bf{e}}_{\bf{1}}}\) is added to it.

Short answer

There exist an edge\({{\bf{e}}_{\bf{2}}}\) in that is not in \({{\bf{T}}_{\bf{1}}}\)such that\({{\bf{T}}_{\bf{1}}}\) remains a spanning tree if \({{\bf{e}}_{\bf{1}}}\)is removed and \({{\bf{e}}_{\bf{2}}}\)is added, and such that remains a spanning tree if \({{\bf{e}}_{\bf{2}}}\)is removed and \({{\bf{e}}_{\bf{1}}}\) is added.

Step-by-step solution

Compare with the definition.

A spanning tree of a plane graph G is a subgraph of G that is a tree and that carry all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit. And a tree with n vertices has \({\bf{n - 1}}\) edges.

The distance between two spanning trees is the number of edges that are not common in the two spanning trees.

Show the result.

Let \({{\bf{e}}_{\bf{1}}}{\bf{ = }}\left( {{\bf{u ,v}}} \right)\).

Since\({{\bf{T}}_{\bf{2}}}\) is a spanning tree and since \({{\bf{e}}_{\bf{1}}}\)is not in \({{\bf{T}}_{\bf{2}}}\).\({{\bf{T}}_{\bf{2}}} \cup {\bf{\{ }}{{\bf{e}}_{\bf{1}}}{\bf{\} }}\)will contain a simple circuit S.

Let \({{\bf{e}}_{\bf{2}}}\)be the edge in the simple circuit S with endpoint v.Such as edge has to exist, else there cannot be a simple circuit and thus\({{\bf{T}}_{\bf{2}}}\) then did not was connected.

\({{\bf{T}}_{\bf{2}}} \cup {\bf{\{ }}{{\bf{e}}_{\bf{1}}}{\bf{\} - \{ }}{{\bf{e}}_{\bf{2}}}{\bf{\} }}\)Is a tree, because \({{\bf{T}}_{\bf{2}}}{\bf{ - \{ }}{{\bf{e}}_{\bf{2}}}{\bf{\} }}\)will contain 2 connected components and \({{\bf{e}}_{\bf{1}}}\)will connect those two components again.

\({{\bf{T}}_{\bf{1}}} \cup {\bf{\{ }}{{\bf{e}}_{\bf{2}}}{\bf{\} - \{ }}{{\bf{e}}_{\bf{1}}}{\bf{\} }}\)Is a tree, because \({{\bf{T}}_{\bf{1}}}{\bf{ - \{ }}{{\bf{e}}_{\bf{1}}}{\bf{\} }}\)will contain 2 connected components and \({{\bf{e}}_{\bf{2}}}\)will connect those two components again.

Therefore,there exist an edge\({{\bf{e}}_{\bf{2}}}\) in that is not in \({{\bf{T}}_{\bf{1}}}\) such that\({{\bf{T}}_{\bf{1}}}\) remains a spanning tree if \({{\bf{e}}_{\bf{1}}}\)is removed and \({{\bf{e}}_{\bf{2}}}\)is added, and such that remains a spanning tree if \({{\bf{e}}_{\bf{2}}}\)is removed and \({{\bf{e}}_{\bf{1}}}\) is added.