Menu
A bowtie is a simple graph on \(5\) vertices with \(6\) edges, which consists of a pair of edge-disjoint triangles having one common vertex. A bowtie design of order \(n\) is an edge-disjoint decomposition of the complete undirected graph \(K_n\) into bowties. These exist if and only if \(n \equiv 1\) or \(9 \pmod{12}\). For any \(n \geq 5\), a maximum packing of the complete undirected graph \(K_n\) with bowties is a collection of edge-disjoint bowties picked from \(K_n\), of maximum cardinality. The unused edges of \(K_n\) in this decomposition, if any, form the leave of the packing, which is necessarily a set with cardinality as small as possible. In this paper, a maximum packing of \(K_n\) with bowties is found, for all \(n \geq 5\) and for all possible leaves.