Proofs of parity results via the Handshaking lemma

Question

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 (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$.

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\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?

Answer 1

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" (Wayback Machine). 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.

Answer 2

There is a nice paper by Kathie Cameron and Jack Edmonds, Some graphic uses of an even number of odd nodes, with several examples of the use of the handshaking lemma to prove various graph-theoretic facts.

Gjergi Zaimi already mentioned the relevance of the complexity classes PPA and PPAD. In addition to Papadimitriou's paper, The relative complexity of NP search problems by Beame et al. (STOC '95) is a useful reference.

I seem to remember that the Chevalley–Warning theorem can be proven by this method, but I can't reconstruct the argument, so maybe I'm confused. EDIT: There is certainly a connection between Chevalley–Warning and PPA—see for example On the Complexity of Modulo-$q$ Arguments and the Chevalley–Warning Theorem—but I'm still not sure if there is proof that directly uses the Handshaking Lemma. EDIT 2: The proof is in the Papadimitriou paper mentioned in Gjergji Zaimi's answer; see Theorems 12 and 13.

Answer 3

The following puzzle can be solved by the same technique. A mountain range is a piecewise linear function $f$ defined on a closed interval $[a,b]$ which satisfies $f(a)=f(b)=0$, and $f(c) > 0$ for all $c \in (a,b)$. There is hiker $A$ at the point $(a,0)$ and a hiker $B$ at the point $(b,0)$. The two hikers begin moving along the mountain range, the only restriction being that they must always be at the same elevation. Prove that $A$ and $B$ can always meet at some point of the mountain range.

On a slightly more serious note, I vaguely remember that the existence of Nash equilibria can be proved by a parity argument (via Sperner's lemma).

As requested by Fedor Petrov in the comments, here is a proof for the mountain range puzzle. Draw a horizontal line through each "valley" or "peak" of the mountain range. Let $P$ be the set of points of the mountain range that intersect these horizontal lines together with the points $(a,0)$ and $(b,0)$. Let $V$ be the set of pairs of points in $P$ which have the same elevation ($y$-coordinate). We interpret each $(p,q) \in V$ to mean that hiker $A$ is at $p$ and hiker $B$ is at $q$. Make a graph $G$ with vertex set $V$ where $(p_1,q_1)$ and $(p_2,q_2)$ are adjacent if the hikers can move from position $(p_1, q_1)$ to position $(p_2,q_2)$ in "one step". Now, it is easy to check that every vertex of $G$ has degree $0, 2$, or $4$, except for $u:=((a,0), (b,0))$ and $v:=((b,0), (a,0))$, which both have degree $1$. By the Handshaking lemma, there is a path from $u$ to $v$ in $G$. Hence, the hikers can reach each other, since there is a sequence of moves that interchanges their starting positions.