Branchings in rooted graphs and the diameter of greedoids (Q1118604)

Let G be a 2-connected rooted graph of rank r and A,B two (rooted) spanning trees of G. We show that the maximum number of exchanges of leaves that can be required to transform A into B is \(r^ 2-r+1(r>0)\). This answers a question by L. Lovász. There is a natural reformulation of this problem in the theory of greeoids, which asks for the maximum diameter of the basis graph of a 2- connected branching greedoid of rank r. Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is \(2^ r-1\).