Proving property of two trees.

Question

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.

Answer 1

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.

Som facts:

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}$.