# How many triads in a graph of size N are needed to cover all possible edges?

As a kid I had a silly dream of trying all possible ice cream pair combinations at Baskin Robbins 31 flavors. I was able to calculate there were $$31\choose 2$$, or 465. At a double scoop a day, that would take over a year.

But then I wondered, how much time would I save ordering only triple scoops? And what price would triple scoops have to be to make this worth it, money-wise?

Looking at the simpler general cases, say, n=4, there are 6 possible pairs: 1-2, 1-3, 1-4, 2-3, 2-4 and 3-4. We can cover them with three triple scoops.

• 1-2-3 adds 12 13 23
• 1-2-4 adds 14 24
• 1-3-4 adds 34

It doesn't look like we can get all the combos in $$\frac{n\choose 2}{3}$$ scoops for just any value of n. If $$n=1 mod 3$$ then n is not even divisible by 3. But we can get close. For n=5, there are 10 possible pairs. We can cover them with four triple scoops.

• 1-2-3 adds 12 13 23
• 1-4-5 adds 14 15 45
• 2-3-4 adds 24 34
• 2-3-5 adds 25 35

For n=6, we take pairs with flavor 1 and get * 1-2-3 * 1-4-5 (note 1-6-x will cover 1-x again, so let's look elsewhere) * 2-4-6 * 3-4-6 * 2-3-5 * 1-5-6

This is 1+$$\frac{n\choose 2}{3}$$, or the best we can do knowing there will be one overlap.

For n=7,

• 1-2-3
• 1-4-5
• 1-6-7
• 2-4-6
• 2-5-7
• 3-4-7
• 3-5-6

But there seems to be no easy way to induct to prove a general case. For instance, going from N to N+3 (or n+any odd number) means we will have to deal with overlapping triads that appear/disappear, N to N+2 means we will eventually hit 1 mod 3, and going from N to N+6 means we can't quite match up (n+1, ..., n+6) into tetrads before pairing them with (1...n). So I'm stuck.

There may be a canonical name for this sort of problem. I'd love to know it.

## 1 Answer

You child dream is real. It was proved by Kirkman in 1847.

We considered this problem a few years ago. We formulated it as follows. Given natural numbers $$n$$ and $$k, find the smallest number $$c(n,k)$$ of copies of a complete graph $$K_k$$, covering all edges of a complete graph $$K_n$$. We were interested in cases $$k=3$$ (as you) and $$k=4$$.

This problem is closely related with Steiner systems. Namely, a required cover without overlapping edges exists iff Steiner system $$S(2,k,n)$$ exists. In particular, for $$k=3$$, $$S(2,k,n)$$ is a Steiner triple system, which exists iff $$n\equiv 1\pmod 6$$ or $$n\equiv 3\pmod 6$$. For instance, you already constructed a Steiner triple system $$S(2,3,7)$$. Also such a system is depicted as the Fano plane at the linked page. Since $$31\equiv 1\pmod 6$$, you can perfectly realize your child dream by triple scoops without overlaps.

Concerning the general case, since a graph $$K_t$$ has $${t\choose 2}$$ edges, we have $$c(n,3)\ge \tfrac {n\choose 2}{3\choose 2}=\tfrac {n(n-1)}{6}.$$ We get an upper bound for $$c(n,3)$$ by adding vertices to the graph $$K_n$$ until a Steiner system exists for $$n$$. It follows that $$c(n,3)\le \tfrac {(n+3)(n+1)}{6}$$. So, asymptotically $$c(n,3)=\frac {n^2}{6}+O(n)$$.