# How to solve a system of XOR equations in a cyclic graph?

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example:

The properties are:

• Each big node (A..H) is connected to at least one blue node
• Each blue node has exactly 3 edges
• The value of each blue node equals the XOR of each connected node.

For this specific case, we have:

0 = A ⊕ B ⊕ C
1 = B ⊕ D ⊕ E
2 = C ⊕ F ⊕ G
3 = B ⊕ C ⊕ D
4 = G ⊕ F ⊕ H
5 = D ⊕ E ⊕ G


I am trying to find if there is a solution. Bruteforce is obviously not a solution :(

• As I'm sure you're aware, XOR-SAT is solvable efficiently.
– cody
Commented May 14 at 21:02
• Not sure what it means to XOR values and get more than 1 though. Are these bitvectors?
– cody
Commented May 14 at 21:03
• @cody It's an XOR operation on a whole binary number, rather than just on single bit. Imagine 3 XOR 5. Convert to binary: 011 XOR 101 = 110. You just apply XOR to each bit 1-by-1, in-line. So XOR first bit in both numbers. XOR second bit, XOR third bit... and so on Commented May 15 at 6:04

You can express this as an instance of XOR-SAT, then find a solution using Gaussian elimination. I am assuming that each value $$1,2,3,$$ represents a bit-vector of some appropriate length, and you are doing bitwise XOR. The variables are the individual bits of $$A,B,C,\dots$$, and each equation yields one clause per bit position.