Parity, cycle space, and K4-subdivisions in graphs

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 cyclesthat generate the cycle space. We explain how thespace generated by the cycles through two prescribed edges in a graph is used in a proof of the conjecturemade by B. Toft in 1974 that every $4$-chromatic graph contains atotally 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 notcontain 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.