Minimum covers of complete graphs by $4$-cycles I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-cycles necessary to cover $K_n$. 
For example, $K_5$ can be covered by following $4$-cycles $(1, 2, 3, 5), (2, 5, 4, 3), (2, 4, 1, 3)$.
I am sure this problem has been studied but unfortunately can't find any results. Can you share some results?
Since $K_n$ has $\binom{n}{2}$ edges, the minimum number of $4$-cycles is obviously at least $\binom{n}{2} / 4$.
 A: If $n$ is odd, the answer is $\lceil \binom{n}{2}/4 \rceil$.
If $n$ is even, the answer is $\lceil \binom{n}{2}/4+n/8 \rceil$.
This follows from two special cases of a more general conjecture by Alspach.  
For our purposes, we use a theorem of Heinrich, Horák, and Rosa which says that if $n \geq 7$ is odd and $a,b,c$ are such that $3a+4b+6c=\binom{n}{2}$, then $E(K_n)$ can be partitioned into $a$ $3$-cycles, $b$ $4$-cycles, and $c$ $6$-cycles. Huang and Fu proved the same result with $(3,4,6)$ replaced by $(4,5)$.
Thus, if $n \geq 7$ is odd, it is always possible to decompose $E(K_n)$ into $4$-cycles and possibly one extra cycle that is a $3$-cycle, a $5$-cycle or a $6$-cycle.  The edge set of the extra cycle can obviously be covered with two $4$-cycles of $K_n$, so we are done. 
If $n$ is even, then each vertex has odd degree.  Let $v$ be an arbitrary vertex.  Since every $4$-cycle uses $0$ or $2$ edges incident to $v$, there will be at least one edge incident to $v$ that is covered twice.  Thus, in total there will be at least $n/2$ edges that are covered twice.  Thus, every covering of $E(K_n)$ by $4$-cycles has size at least $\binom{n}{2}/4+n/8$. We prove that this bound can actually be achieved.  
Namely, for $n$ even, Heinrich, Horák, and Rosa's result holds except with $K_n$ replaced by $K_n$ minus a perfect matching $M$, and $\binom{n}{2}$ replaced with $\frac{n(n-2)}{2}$. For $n$ even, $\frac{n(n-2)}{2}$ is divisible by $4$.  It follows that the edges of $K_n-M$ can be decomposed into $4$-cycles. By then covering pairs of edges of $M$ with $4$-cycles we get a covering of size $\lceil \binom{n}{2}/4+n/8 \rceil$.  
A: If n is even, you can form a partial edge cover with disjoint four-cycles: pick points u and v, and cover all edges coming from u and from v (except for uv) by disjoint cycles. Now recurse, leaving n/2 uncovered edges which are covered by n/4 many more cycles.  If n is odd, save edges coming from w for later, and cover the remaining n-1 points and edges, leaving 3(n-1)/2 edges to be covered three at a time by cycles going through w.  This gives a minimum of about n/4 + n(n-2)/8 many cycles, with exact numbers to come later.
Edit: Tony Huynh has provided exact numbers, with the construction in the paragraph above an alternate proof for even n.  For odd n greater than 3, the cycle decomposition using an extra 3 5 or 6 cycle improves on the method above.  End Edit.
Gerhard "Bed For Now. Calculations Later." Paseman, 2017.08.29.
