# Partitioning a graph in cycles of four

I have the following question:

Suppose that in a simple undirected graph with $4n$ vertices, each vertex has degree at least $2n$.

Is it true that we can always partition the set of vertices in $n$ parts of size $4$ such that the vertices of every part can form a cycle (of length $4$)?

I was able to prove only that it is possible to find $4$ vertices that form a cycle.

• This was a conjecture of Erdős and Faudree resolved in this 2010 paper. – Misha Lavrov Nov 23 '17 at 1:06
• @MishaLavrov: Excelent! – digital-Ink Nov 23 '17 at 16:11
• Wow! A proof over 40 pages. No wonder I couldn't solve it in one day! – digital-Ink Nov 23 '17 at 16:30