Forcing a 2-regular minor

Importance: Medium ✭✭
Keywords: minors
Recomm. for undergrads: yes
Posted by: David Wood
on: March 16th, 2014
Conjecture   Every graph with average degree at least $ \frac{4}{3}t-2 $ contains every 2-regular graph on $ t $ vertices as a minor.

Reed and Wood [RW] explained that a result of Corradi and Hajnal [CH] implies that if $ H $ is the graph consisting of $ k $ disjoint triangles, then every graph with average degree at least $ 4k-2 $ contains $ H $ as a minor. Moreover, the bound of $ 4k-2 $ is best possible since the complete bipartite graph $ K_{2k-1,n} $ contains no $ H $-minor, but has average degree tending to $ 4k-2 $ (as $ n\rightarrow\infty $). Thus the conjecture would generalise this result.


[CH] Keresztely Corradi and Andras Hajnal. On the maximal number of independent circuits of a graph. Acta Math. Acad. Sci. Hungar., 14:423–443, 1963.

*[RW] Bruce Reed and David R. Wood. Forcing a sparse minor, arXiv:1402.0272, 2013.

* indicates original appearance(s) of problem.