On Orthogonal Double Covers of \(K_n\)

Abstract

An orthogonal double cover of the complete graph \(K_n\) is a collection of \(n\) spanning subgraphs \(G_1, G_2, \ldots, G_n$ of \(K_n\) such that every edge of \(K_n\) belongs to exactly 2 of the \(G_i\)’s and every pair of \(G_i\)s intersect in exactly one edge.
It is proved that an orthogonal double cover exists for all \(n \geq 4\), where the \(G_i\)’s consist of short cycles; this result also proves a conjecture of Chung and West.