Parity, Cycle Space, and K4-Subdivisions in Graphs
Carsten Thomassen · Cambridge University Press eBooks · 1999
We survey some parity arguments and problems in graph theory, in particular some that can be attacked using the cycle space of a graph. We discuss some results on specific collections of cycles that generate the cycle space. We explain how the space generated by the cycles through two prescribed edges in a graph is used in a proof of the conjecture made by B. Toft in 1974 that every 4-chromatic graph contains a totally odd K 4 -subdivision, that is, a subdivision of K 4 in which each edge of K 4 corresponds to an odd path. (Another proof of Toft's conjecture was found independently by W. Zang). We prove the new result that every 4-connected graph with at least three triangles contains a totally odd K 4 -subdivision if and only if it does not contain a vertex whose deletion results in a bipartite graph. In particular, every 4-connected planar graph contains a totally odd K 4 -subdivision. Finally, we offer some conjectures on path systems and subdivisions with parity constraints on the lengths. Introduction Parity arguments are often both elegant and powerful. An early parity result in graph theory is Redei's theorem [12] saying that the number of directed Hamiltonian paths in any tournament is odd. It implies, in particular, that every tournament has a directed Hamiltonian path. While this is an easy exercise, Redei's theorem inspired Forcade [4] to a parity result where the corresponding existence result is highly nontrivial.