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:
-
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.
-
(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 (parity of degrees of $x$ and $y$ 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$. They are the vertices of a new graph. 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 than the 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$.
-
(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\setminus A$ has at least one neighbor in $A$. Then any graph has an 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 a general question: what are other examples of such flavor? Of course, proving of parity by partitioning onto pairs formally is a 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?
Best Answer
Another very famous example is Sperner's lemma. Other examples are Chevalley's theorem for $p=2$, Tucker's lemma, the fact that the number of decompositions into Hamiltonian cycles is even etc. (See the paper below). The continuous analogs of some of these are also derived from the same proofs, therefore you could count Brower's fixed point theorem (from Sperner's lemma) and Borsuk-Ulam theorem and the Ham-Sandwich theorem (from Tucker's lemma), as following from the handshake lemma.
On the other hand you may be interested in the complexity classes PPA and PPAD which provide one possible formalization of your question. There are a lot of papers (in complexity theory) that study such examples, but I can't comment further since I'm not very familiar with the literature. One place to start is the article by Christos Papadimitriou (1994), "On the complexity of the parity argument and other inefficient proofs of existence". Journal of Computer and System Sciences 48 (3): 498–532. I thought this was relevant since you mention that you want problems which can be solved by a parity argument but the graph involved is complex enough that it is not easy to exhibit an involution.