Importance: Medium ✭✭
 Author(s): Reed, Bruce A. Wood, David R.
 Subject: Graph Theory » Basic Graph Theory » » Minors
 Keywords: minors
 Posted by: David Wood on: March 16th, 2014
Conjecture   Every graph with average degree at least contains every 2-regular graph on vertices as a minor.

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

## Bibliography

[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.