The Dependence Graph for Bases in Matroids

This paper discusses a certain graph, called the 'dependence graph' ('the DPG'), that can be defined naturally for a given independent set in a matroid. The author is mainly concerned with the DPG of bases, and the author studies what the DPG of a base tells about the matroid. It is shown that there is a nice connection between the DPG and duality, and between the DPG and connectivity for matroids. This last fact leads to an algorithm for determining the connected components of a matroid and also to one for computing a circuit containing two given distinct elements in the same such component. A simple algorithm using depth-first search is given for solving this last problem for graphic matroids.