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:Theorem – A graph G=(V,E) is a basis graph of an even Δ-matroid if and only if it satisfies the following conditions:(a)if x1x2x3x4 is a square and b∈V, then d(b,x1)+d(b,x3)=d(b,x2)+d(b,x4);(b)each 2-interval of G contains a square and is an induced subgraph of the 4-octahedron;(c)the neighborhoods of vertices induce line graphs, or, equivalently, the neighborhoods of vertices do not contain induced 5- and 6-wheels. (A 2-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.)