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.

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.