 Solution

For an $r$-uniform set family $\mathcal{F}$, its lower shadow is the set family of all $(r-1)$-sets contained in a member. Write a positive integer $m$ in its unique binomial representationThe Kruskal-Katona theorem states thatFor $m=0$ the bound is zero. Equality is attained by the first $m$ $r$-sets in colexicographic order. In that order $A$ precedes $B$ when the largest element of their symmetric difference belongs to $B$.

Here is a complete UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-sized sets $U,V$, put $C(A)=(A\setminus V)\cup U$ when $A$ contains every element of $V$ and no element of $U$, and put $C(A)=A$ otherwise. The UV-compression of a set family replaces an eligible $A$ only if its image is absent. It preserves cardinality: a retained collision keeps both the original set and its already present image.

We first prove the required Shadow lemma for UV-compressions. Suppose that, for each $x\in U$, a $y\in V$ can be chosen so the set family is fixed by $C_{U\setminus \{x\},V\setminus \{y\}}$. We claimConsider a lower shadow member obtained by deleting $z$ from a moved set $A^{\prime }=(A\setminus V)\cup U$. If $z\notin U$, it is the compressed image of $A\setminus \{z\}$, an old lower shadow member. If $z=x\in U$, the smaller compression of $A$ produces $A^{\prime }\setminus \{x\}\cup \{y\}$, which is in $\mathcal{F}$ by the assumed invariance. Thus $A^{\prime }\setminus \{x\}$ already belongs to the old lower shadow; it is not eligible to move since it lacks $x$.

It remains to consider a lower shadow member $B$ from a retained original member $A=B\cup \{z\}$. If $B$ is not eligible to move, it stays in the compressed lower shadow. If it is eligible, let $B^{\prime }=(B\setminus V)\cup U$. When $z\notin U$, retaining the eligible $A$ means its image already belongs to $\mathcal{F}$, and that image contains $B^{\prime }$. When $z=x\in U$, the smaller compression of $A$ belongs to $\mathcal{F}$ and equals $B^{\prime }\cup \{y\}$. In either case $B^{\prime }$ is in the old lower shadow too. Consequently the collision rule retains $B$ as well. This proves the claimed containment in every case. Since compression preserves cardinality, it cannot increase lower shadow size.

If $\mathcal{F}$ is not a colexicographic initial segment, an earlier absent set $A$ and a later present set $B$ give $U=A\setminus B$, $V=B\setminus A$ with $\max U<\max V$, and a nontrivial UV-compression. Choose such a compression with $|U|$ smallest. If $|U|>1$, choose $y\in V\setminus \{\max V\}$. For every $x\in U$, the smaller compression still has its largest differing element on the $V$ side and must fix $\mathcal{F}$ by minimality. If $|U|=1$, the smaller compression is the identity. Thus the lower shadow argument applies.

Each nontrivial step strictly decreases the positive integer weightbecause the largest differing coordinate belongs to $V$. Iteration therefore terminates. A terminal set family is a colexicographic initial segment, since an earlier gap and a later member would otherwise provide another nontrivial compression. The final set family has $m$ members and no larger lower shadow.

To compute its lower shadow, take $a_r$ maximal with $\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)\le m$. All $r$-sets of $[a_r]$ occur first. The next block consists of sets containing $a_r+1$ whose remaining $(r-1)$-set runs through the initial segment of length $m-\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)$. By Pascal's identity, the remainder is smaller than $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$, so its next leading top index is strictly less than $a_r$. Repeating gives the stated unique binomial representation. The first block contributes all $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ $(r-1)$-sets in $[a_r]$ to the lower shadow. Deleting $a_r+1$ from the next block contributes only sets already counted; deleting another coordinate contributes $a_r+1$ joined to the lower shadow of the smaller initial segment. This recursive decomposition gives exactly the displayed sum. The base $r=1$ has lower shadow $\{\varnothing \}$ for every nonempty set family. This completes the proof and the sharpness assertion.

Now let $\mathcal{C}$ be the set family of vertex sets of the graph's cliques of order four. Its twice-iterated lower shadow consists of edges of the graph. If there were at least sixteen such copies, choose a sixteen-member subfamily. The relevant binomial representation isThe proved theorem gives at least $\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)=23$ triples in its first lower shadow. Apply it again to any twenty-three of those triples, using $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Their edge lower shadow has at leastmembers, contradicting the fifteen available edges. Conversely, the complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges and $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$ copies of $K_4$. Therefore the maximum number of copies is exactly 15.