  In Graph Theory a number of results were devoted to studying the
computational complexity of the number modulo 2 of a graph's edge set
decompositions of various kinds, first of all including its Hamiltonian
decompositions, as well as the number modulo 2 of, say, Hamiltonian
cycles/paths etc. While the problems of finding a Hamiltonian decomposition and
Hamiltonian cycle are NP-complete, counting these objects modulo 2 in
polynomial time is yet possible for certain types of regular undirected graphs.
Some of the most known examples are the theorems about the existence of an even
number of Hamiltonian decompositions in a 4-regular graph and an even number of
such decompositions where two given edges e and g belong to different cycles
(Thomason, 1978), as well as an even number of Hamiltonian cycles passing
through any given edge in a regular odd-degreed graph (Smith's theorem). The
present article introduces a new algebraic technique which generalizes the
notion of counting modulo 2 via applying fields of Characteristic 2 and
determinants and, for instance, allows to receive a polynomial-time formula for
the number modulo 2 of a 4-regular bipartite graph's Hamiltonian decompositions
such that a given edge and a given path of length 2 belong to different
Hamiltonian cycles - hence refining/extending (in a computational sense)
Thomason's result for bipartite graphs. This technique also provides a
polynomial-time calculation of the number modulo 2 of a graph's edge set
decompositions into simple cycles each containing at least one element of a
given set of its edges what is a similar kind of extension of Thomason's
theorem as well.
