Basis graphs of even Delta-matroids

A Δ-matroid is a collection B of subsets of a finite set I, called bases, not necessarily equicardinal, satisfying the symmetric exchange property: For A , B ∈ B and i ∈ A Δ B , there exists j ∈ B Δ A such that ( A Δ { i , j } ) ∈ B . A Δ-matroid whose bases all have the same cardinality modulo 2 is called an even Δ-matroid. The basis graph G = G ( B ) of an even Δ-matroid B is the graph whose vertices are the bases of B and edges are the pairs A , B of bases differing by a single exchange (i.e., | A Δ B | = 2 ). In this note, we present a characterization of basis graphs of even Δ-matroids, extending the description of basis graphs of ordinary matroids given by S. Maurer in 1973: m h G = ( V , E ) is a basis graph of an even Δ-matroid if and only if it satisfies the following conditions:(a) x 2 x 3 x 4 is a square and b ∈ V , then d ( b , x 1 ) + d ( b , x 3 ) = d ( b , x 2 ) + d ( b , x 4 ) ; -interval of G contains a square and is an induced subgraph of the 4-octahedron; ighborhoods of vertices induce line graphs, or, equivalently, the neighborhoods of vertices do not contain induced 5- and 6-wheels. interval is the subgraph induced by two vertices at distance 2 and all their common neighbors; a square is an induced 4-cycle of G.)