On matroids with many common bases Original Research Article

Let B(M) denote the collection of bases of a matroid M. Truemper showed that if M1 and M2 are connected matroids having the same ground set and the symmetric difference B(M1)ΔB(M2) has cardinality one, then one of M1 and M2 is obtained from the other by relaxing a circuit-hyperplane. This paper shows that, apart from a trivial exception, a pair of connected matroids M1 and M2 having the same ground set and the property that |B(M1)ΔB(M2)|=2 must also be related via the relaxation operation.