Random partitions and edge-disjoint Hamiltonian cycles

In this paper we prove a similar result using methods that do not rely on the Regularity Lemma. In particular, we prove that every graph on n vertices with minimum degree δ⩾n/2+3n3/4ln(n) contains α(δ,n)/2−3n7/8(lnn)1/4/2 edge-disjoint Hamiltonian cycles. Our proof rests on a structural result that is of independent interest: let G be a graph on n vertices, where n=pq. Then there exists a partition of the vertices of G into q parts of size p such that every vertex v has at least deg(v)/q−min{deg(v),p}⋅ln(n) neighbors in each part.