# Proving property of two trees.

Consider a graph $$G$$. Let $$A, B$$ are two trees in a graph and $$T_a, T_b$$ represents their corresponding edge sets. Also an edge $$e \in E$$ is an extension of tree $$A$$. If $$T_b \cup \{e\}$$ forms a cycle then exactly one of the following holds:

1. There exists an edge $$e_b \in T_b$$ which is also an extension of tree A
2. For all $$e_b \in T_b$$, $$T_a \cup \{e_b\}$$ forms a cycle.

An edge $$e \notin T_a$$ is an extension of tree $$A$$ if $$T_a \cup \{ e \}$$ also forms a tree.

Actually, I am trying to prove that collection of edge sets which induce trees is a connected sub matroid of a graphic matroid. I have proved remaining 3 properties of a connected sub matroid but struck at this one.

• What is an extension of a tree? Sep 28, 2018 at 17:24
• Do the trees use all vertices of $G$? Sep 28, 2018 at 17:25
• @HagenvonEitzen No not necessarily. Sep 28, 2018 at 17:26
• @AndrewUzzell Updated. Sep 28, 2018 at 17:26
• If $A=B$, the claim is clearly false. Sep 28, 2018 at 17:38

My thesis is: there exists an edge $$e_{b}\in T_{b}$$ which is also an extension in $$A$$. Thus I claim your statement is true, but the second point is not needed.
1. $$e$$ has exactly one vertex in $$A$$, because it's an extension
2. $$e$$ has exactly two vertices in $$B$$, because it forms cycle
3. $$A$$ and $$B$$ have a common vertex, let's name it Paul
Let's assume that my thesis is false. This means there doesn't exist any edge from $$T_{b}$$ that is an extension of $$A$$. It means that Pauls neighbors from $$B$$ are in $$A$$. From that we get more Pauls (common vertices), all their neighbors (from $$B$$) are in $$A$$ also, because otherwise we would find the extension of $$A$$ (*). Because $$B$$ is connected, we get to the point, where one of the Pauls is adjacent to the second end of $$e$$. For the assumtion to be true, we get that both ends of $$e$$ are in $$A$$. And that can't be true for $$e$$ to be an extension.
(*) - there is one thing that could stop Pauls expansion in $$B$$. Its when we get to a common edge of $$A$$ and $$B$$, as the edge that is already in $$T_{a}$$ is not As extension. But the edges after it can be the extension, so we "jump". And actually there are edges to jump (edges that are not in $$T_{a}$$), because $$e$$ has exactly one vertex in $$A$$, so at least one edge has to be in $$T_{b}$$ and not in $$T_{a}$$.