In mathematics, a delta-matroid or Δ-matroid is a family of sets obeying an exchange axiom generalizing an axiom of matroids.
For the basis sets of a matroid, the corresponding exchange axiom requires in addition that
[1] An alternative and equivalent definition is that a family of sets forms a delta-matroid when the convex hull of its indicator vectors (the analogue of a matroid polytope) has the property that every edge length is either one or the square root of two.
[3][4] Delta-matroids have also been used to study constraint satisfaction problems.
[5] As a special case, an even delta-matroid is a delta-matroid in which either all sets have even number of elements, or all sets have an odd number of elements.
If a constraint satisfaction problem has a Boolean variable on each edge of a planar graph, and if the variables of the edges incident to each vertex of the graph are constrained to belong to an even delta-matroid (possibly a different even delta-matroid for each vertex), then the problem can be solved in polynomial time.
This result plays a key role in a characterization of the planar Boolean constraint satisfaction problems that can be solved in polynomial time.