Circuits through edges

The following is a summary of the paper Circuits through prescribed edges which is joint work with Max Pitz. In 2020 it was published in Journal of Graph Theory, Volume 93, Issue 4, Page 470-482. You can find a preprint on arXiv. This paper is an extract from my Bachelor's thesis, which I created under the supervision of Max. He did an absolutely amazing job, especially in guiding my first steps in research. This may be one of the big reason which enabled me to follow this path further.

Main result: Given a connected graph G and a natural number k, every set of k edges lies on a common circuit if and only if G has no odd cut of size at most k.

Context: A rather simple question to ask is: when do k prescribed edges of a graph lie on a common cycle? Lovasz (1973) and independently also Woodall (1977) conjectured that 

Every k pairwise independent edges on a k-connected graph lie on a common cycle, if k is even or if after its deletion the graph is still connected. 

Building on Woodall's 'Hopping Lemma' technique, Häggkvist & Thomassen (1982) and Kawarabayashi (2002) showed two weakenings of the Lovasz-Woodall-Conjecture: Häggkvist & Thomasssn set out from the stronger assumption of (k+1)- instead of k-connectedness, and Kawarabayashi obtained a weaker conclusion, namely, at most two vertex-disjoint cycles instaead of one.

A relaxation of the concept of cycles are circuits: Formally, a cycle may be described as a cyclic sequence alternating between vertices and edges such that the predecessor and the successor of every edge are both its endvertices and in which no vertex appears twice. A circuit is a cyclic sequence such as cycles  in which vertices now may appear multiple times but no edge appears twice. 

In light of the above mentioned Lovasz-Woodall-Conjecture, it is natural to ask: When do k prescribed edges in a graph lie on a common circuit? Our main result answers this question by giving a sufficient global condition: the underlying graph is connected and has no odd cut of size at most k; in particular, every graph with edge-connectivity at least 2·ceil(k/2) satisfies this condition. Our proof heavily relies on an adaption of Woodall's Hopping Lemma technique to edge-connectivity.