Return to Answer

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.

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.

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.

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.

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, this paper by Beame et al. 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.

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.