On regular packings and coverings

NEW

Problem: Formalized literally: for all admissible integers $t$, the graphs/multigraphs

decompose into copies of $K_4$, where $C_n$ is a Hamiltonian cycle and $+$ means adding a second parallel copy of the cycle edges. The text supports this because these are exactly the residue classes where the usual degree and edge-count divisibility obstructions for $K_4$-decomposition are repaired by deleting/adding a Hamiltonian cycle.

Result: The literal statement is false. Take $t=1$ in the first family: $K_{12}-C_{12}$ has no $K_4$-decomposition.

Label the Hamiltonian cycle $0,1,\dots,11,0$. If a decomposition existed, it would contain

copies of $K_4$. Each block must be a 4-subset with no cyclically consecutive vertices.

For such a block $B$, let $p_i(B)$ be the number of pairs of vertices of $B$ at cyclic distance $i$, for $i=2,3,4,5,6$. Across the whole decomposition the required total is

since there are 12 pairs at each distance $2,3,4,5$, and 6 opposite pairs at distance $6$.

The possible cyclic gap patterns for an independent 4-subset of $C_{12}$, up to rotation/reflection, and their profiles $(p_2,p_3,p_4,p_5,p_6)$, are:

Solving the resulting linear count equations forces exactly six blocks of type $(2,3,4,3)$ and three blocks of type $(2,4,2,4)$, with no other types.

Now let $P_i=\{i,i+6\}$, $i\in\mathbb Z_6$, be the six opposite pairs. A block of type $(2,4,2,4)$ is necessarily of the form

so it contains exactly the two opposite pairs $P_i$ and $P_{i+2}$. Thus the three type-$(2,4,2,4)$ blocks would have to form a perfect matching in the graph on $\{P_0,\dots,P_5\}$ with edges $P_iP_{i+2}$. But this graph is the disjoint union of two triangles, hence has no perfect matching. Contradiction.

Therefore $K_{12}-C_{12}$ cannot be decomposed into $K_4$'s. The conjecture needs at least the missing small-order exception $t=1$ in the $K_{12t}-C_{12t}$ case.

Citation: No external counterexample is used; the disproof above is direct. The conjecture source is Bermond–Bond–Sotteau, “On regular packings and coverings,” Annals of Discrete Mathematics 34 (1987), 81–100.