Decomposing graphs into edges and triangles

Daniel Král', Bernard Lidický, Taísa L. Martins +1

We prove the following 30-year old conjecture of Győri and Tuza: the edges of every $n$-vertex graph $G$ can be decomposed into complete graphs $C_1,\dots ,C_{\ell }$ of orders two an…