Identities obtained by elementary finite Fourier analysis are used to derive a variety of evaluations of the Tutte polynomial of a graph G on the hyperbolae H_2 and H_4. These evaluations are expressed in terms of eulerian subgraphs of G and the size of subgraphs modulo 2,3,4 or 6. In particular, a graph is found to have a nowhere-zero 4-flow if and only if there is a correlation between the event that three subgraphs A, B, C chosen uniformly at random have pairwise eulerian symmetric differences and the event that the integer part of ( |A| + |B| + |C| ) / 3 is even. Further, the connection between results of Matiyasevich, Alon and Tarsi, and Onn is highlighted by indicating how they may all be derived by the techniques adopted in this paper.
|Translated title of the contribution||Parity, eulerian subgraphs and the Tutte polynominal|
|Pages (from-to)||599 - 628|
|Number of pages||30|
|Journal||Journal of Combinatorial Theory Series B|
|Publication status||Published - May 2008|
Bibliographical notePublisher: Elsevier