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 mention three results of such nature:

1. If the graph $G$ has even number of vertices and all of them have even degree, then it has even number of spanning trees. It may be proved by using the matrix-tree theorem, though not immediately, I mean the following elementary argument: consider the new graph, in which spanning trees of $G$ serve as vertices, and two trees $T$, $T'$ are joined iff they differ by one edge (i.e. all edges of $T$ except one edge are also edges of $T'$). Then all degrees in new graph are odd and we are done.

2. (This argument is due to Andrew Thomason). Given vertices $x$, $y$ in a finite graph $G$, in which all vertices except $x$, $y$ have odd degree ($x$ and $y$ may have both even degree or moth odd, it does not matter), then the number of Hamiltonian paths from $x$ to $y$ is even. For proving this, consider all Hamiltonian paths starting in $y$ in the graph $G-x$. Join two such paths if they differ by one edge (i.e. all edges of the first path except one are also edges of the second). Then the degree of a path $yz\dots v$ in new graph is one less then degree of $v$ in $G-x$. So, it is odd iff $v$ is joined to $x$, and odd vertices of our new graph correspond to Hamiltonian paths from $x$ to $y$ in $G$.

3. (This is due to László Lovász). Let $G=(V,E)$ be a finite graph. Call a subset $A\subset V$ dominating if any vertex $v\in V\subset A$ has at least one neighbor in $A$. Then any non-empty graph has odd number of dominating sets. We prove that the number of non-dominating non-empty subsets of $V$ is even. They are vertices of a new graph, and two of them $B_1,B_2$ are joined iff there are no edges between $B_1$ and $B_2$ in $G$. All degrees are odd (degree of $B$ equals $2^k-1$, where $k$ is the number of vertices in $V\subset B$ not joined with $B$), and we are done again.

I have general question: what are other examples of such flavor? Of course, proving of parity by partitioning onto pairs formally is particular case (corresponding to the graph with degrees 1), and by partitioning onto even subsets too, but I rather ask about more involved graphs used in the proof:)

And one specific question: may Redei's result that any tournament have odd number of Hamiltonian paths be proved by such techniques?