On a base exchange game on bispanning graphs

We consider the following maker–breaker game on a bispanning graph   i.e. a graph that has a partition of the edge set EE into two spanning trees E1E1 and E2E2. Initially the edges of E1E1 are purple and the edges of E2E2 blue. Maker and breaker move alternately. In a move of the maker a blue edge is colored purple. The breaker then has to recolor a different edge blue in such a way that the purple and the blue edges are spanning trees again. The goal of the maker is to exchange all colors, i.e. to make E1E1 blue and E2E2 purple. We prove that a sufficient but not necessary condition for the breaker to win is that the graph contains a K4K4. Furthermore we characterize the structure of a partition of a wheel into two spanning trees and show that the maker wins on wheels WnWn with n≥4n≥4 and provide an example of a graph where, for some partitions, the maker wins, for some others, the breaker wins. We also describe an efficient algorithm for the recognition of bispanning graphs.