Dr. Kathie Cameron, Wilfrid Laurier University

Parity Theorems and Exchange Graph Algorithms concerning Paths, Cycles and Trees

Carsten Thomassen and I proved that in any graph G, the number of cycles containing a specified edge as well as all the odd-degree vertices is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Sunichi Toida and where all vertices have odd degree it is Andrew Thomason's generalization of Smith's Theorem.

Kenneth Berman extended Thomason’s Theorem to trees: he used a counting argument to prove that if T is a spanning tree of a graph G where all vertices in G-E(T) have odd degree, there is an even number of spanning trees of G with the same degree as T at each vertex.

I give a common generalization of these results to a parity theorem about (not necessarily spanning) trees.

Andrew Thomason proved his theorem by constructing a graph X(G), his lollipop graph, in which the odd-degree vertices correspond precisely to the things he wants to show there are an even number of, namely the hamiltonian cycles in G containing the specified edge. Christos Papadimitriou calls this approach the polynomial parity argument (PPA). It provides an algorithm for given one of the objects, finding another, by walking in X(G) from one odd-degree vertex to another.

I have extended Thomason's algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices, and more generally finds a second tree with certain properties. I will discuss these algorithms and some other parity theorems.