Graph Theory37 sections · 1633 units
Open in Course

Constraint Pattern - Exactly One

(One must be true)

To enforce "exactly one of x, y is true," combine two constraints. First: at least one is true, that is x OR y. This is standard 22-SAT. Second: at most one is true, that is NOT x OR NOT y. Together: exactly one. You can generalize this to more variables with care.

For more than two variables, the "at least one" part needs auxiliary variables to stay in 22-SAT. The "at most one" part uses the pairwise pattern from before. Three variables requires more clauses.