Problem #577: If $G$ is a graph with $4k$ vertices and minimum degree at...

If $G$ is a graph with $4k$ vertices and minimum degree at least $2k$ then $G$ contains $k$ vertex-disjoint $4$-cycles.

SOLVED

Problem Statement

If $G$ is a graph with $4k$ vertices and minimum degree at least $2k$ then $G$ contains $k$ vertex-disjoint $4$-cycles.

Categories: Graph Theory

A conjecture of Erdős and Faudree. Proved by Wang [Wa10].

Source: erdosproblems.com/577 | Last verified: January 15, 2026