The Parity of a Thicket

Abstract

A thicket in a graph $G$ is defined as a set of even circuits such that every edge lies in an even number of them. If $G$ is directed, then each circuit in the thicket has a well defined directed parity. The parity of the thicket is the sum of the parities of its members, and is independent of the orientation of $G$. We study the problem of determining the parity of a thicket $\mathcal{T}$ in terms of structural properties of $\mathcal{T}$. Specifically, we reduce the problem to studying the case where the underlying graph $G$ is cubic. In this case we solve the problem if $|\mathcal{T}| = 3$ or $G$ is bipartite. Some applications to the problem of characterising Pfaffian graphs are also considered.