Kathie Cameron kcameron@mach1.wlu.ca
and Jack Edmonds jedmonds@math.uwaterloo.ca
Perhaps the simplest useful theorem of graph theory is that every graph X has an even number of odd (degree) nodes. We give new proofs of several theorems each of which asserts that, for any input G satisfying specified conditions, G has an even (or odd) number of H's satisfying specified conditions. Each proof consists of describing an "exchange graph" X, quite large compared to G, such that the odd nodes of X are the objects H which we want to show there is an even number of.
Each of these theorems is not so easy to prove without seeing the exchange graph. They include as corollaries the results of Andrew Thomason proving the 1965 conjecture of Lin that the union of any two edge-disjoint hamiltonian circuits of any graph G is also the union of two other edge-disjoint hamiltonian circuits of G (and hence two edge-disjoint hamiltonian circuits of any graph G is also the union of two other edge-disjoint hamiltonian circuits of G (and hence two edge-disjoint hamiltonian circuits of G can not be neighbour vertices in the convex hull of the hamiltonian circuits of G). They include Berman's generalization of Thomason's generalization of the famous Smith theorem, that each edge in a cubic graph G is in an even number of hamiltonian circuits of G.