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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.