Binary nullity, Euler circuits and interlace polynomials

A theorem of Cohn and Lempel [M. Cohn, A. Lempel, Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A 13 (1972) 83–89] gives an equality relating the number of circuits in a directed circuit partition of a 2-in, 2-out digraph to the GF(2)GF(2)-nullity of an associated matrix. This equality is essentially equivalent to the relationship between directed circuit partitions of 2-in, 2-out digraphs and vertex-nullity interlace polynomials of interlace graphs. We present an extension of the Cohn–Lempel equality that describes arbitrary circuit partitions in (undirected) 4-regular graphs. The extended equality incorporates topological results that have been of use in knot theory, and it implies that if HH is obtained from an interlace graph by attaching loops at some vertices then the vertex-nullity interlace polynomial qN(H)qN(H) is essentially the generating function for certain circuit partitions of an associated 4-regular graph.