@bof It's not really that I add it, it is that it can not be otherwise. In $K_{2n}$ every vertex has degree $2n-1$ so that if you decompose your graph into $n$ paths, every vertex will play the role of a degree 2 vertex $n-1$ times, and the role of an extremity once. Now if the two extremities had the same label, only the vertices with the same label would be able to play the role of an extremity so it wouldn't be possible.

@bof It is necessary : since every vertex is going to play the role of an extremity exactly once, the extrimities must have distinct label, and each of them is represented exactly $n$ times, so each of the two labels is present n times.

@monkeymaths Indeed, sorry, I am imposing that there are exactly two distinct labels, so not just a's or b's.

@domotorp I'm trying to prove a graph theory conjecture saying that every digraph with less than $2n-4$ edges admits a packing with itself, and it's equivalent to say that every of those sets with cardinality $2n-4$ does not cover all the permutations, this is why only the minimum value is interesting in this case. I thought it would be easier to see it this way but I guess not.

@ZachTeitler Thanks. For $n=4$ the minimum is 4 too. I'm actually trying to prove that the minimal cardinality is greater than $2n-4$ $\forall n$. I wrote a script that was able to test it until $n=12$ only.

@coudy Sorry, the $x_i$ are not necessarily distinct, only the couples are. By [n] I mean the integers from 1 to $n$, and the smallest set is the set which has the smallest cardinality.

@ThomasKalinowski Thank you for the help, I'll explore the equivalent formulations. The last necessary condition is still not enough unfortunately.

@GerhardPaseman Thanks a lot, I will look it up !

@FedorPetrov Thank you. I actually saw this one, unfortunately it is not enough in my case. I feel like we are considering that each of the intersecting pairs provided by the elements are independent while they are linked by the fact that each set has $q$ elements.

@GerryMyerson Thank you, that's exactly what I needed !