Bonds with parity constraints

Given a connected graph G=(V,E) and three even-sized subsets A1, A2, A3 of V, when does V have a partition (S1,S2) such that G[Si] is connected and |Si∩Aj| is odd for all i=1,2 and j=1,2,3? This problem arises in the area of integer flow theory and has theoretical interest in its own right. The special case when |A1|=|A2|=|A3|=2 has been resolved by Chakravarti and Robertson, and the general problem can be rephrased as a problem on binary matroids that asks if a given triple of elements is contained in a circuit. The purpose of this paper is to present a complete solution to this problem based on a strengthening of Seymourʼs theorem on triples in matroid circuits.