  Let $\mathcal S$ be a family of subsets of a set $X$ of cardinality $m$ and
$\text{VC-dim}(\mathcal S)$ be the Vapnik-Chervonenkis dimension of $\mathcal
S$. Haussler, Littlestone, and Warmuth (Inf. Comput., 1994) proved that if
$G_1(\mathcal S)=(V,E)$ is the subgraph of the hypercube $Q_m$ induced by
$\mathcal S$ (called the 1-inclusion graph of $\mathcal S$), then
$\frac{|E|}{|V|}\le \text{VC-dim}({\mathcal S})$. Haussler (J. Combin. Th. A,
1995) presented an elegant proof of this inequality using the shifting
operation.
  In this note, we adapt the shifting technique to prove that if $\mathcal S$
is an arbitrary set family and $G_{1,2}(\mathcal S)=(V,E)$ is the 1,2-inclusion
graph of $\mathcal S$ (i.e., the subgraph of the square $Q^2_m$ of the
hypercube $Q_m$ induced by $\mathcal S$), then $\frac{|E|}{|V|}\le
\binom{d}{2}$, where $d:=\text{cVC-dim}^*(\mathcal S)$ is the
clique-VC-dimension of $\mathcal S$ (which we introduce in this paper). The
1,2-inclusion graphs are exactly the subgraphs of halved cubes and comprise
subgraphs of Johnson graphs as a subclass.
