The parity tag has no wiki summary.

**10**

votes

**3**answers

932 views

### Proofs of parity results via the Handshaking lemma

I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...

**6**

votes

**2**answers

863 views

### How hard is it to solve SAT if the promise is that it has an odd number of solutions?

SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known ...