Characterization of finite VC-dimension I have heard the following claim (which I hope to repeat correctly)

A graph $E\subseteq U\times V$ has finite VC-dimension if and only if there is a largest $n$ such that all graphs $G\subseteq X\times Y$ with $|X|,|Y|<n$ can be embedded in $E\subseteq U\times V$.

I forgot where I heard it. No proof or reference was given.
 A: First let me make sure that we agree about what it means for a bipartite graph $E \subseteq U\times V$ to have finite VC-dimension. It'll be useful to fix some notation.
For $v\in V$, let $E_v = \{u\in U\mid uEv\}$. Let's say $E$ is extensional if $E_v = E_{v'}$ implies $v = v'$.
For $A\subseteq U$, we say $E$ shatters $A$ if for all $B\subseteq A$ there exists $v_B\in V$ such that $B = A\cap E_{v_B}$. We say $E$ has finite VC-dimension if there is some $n\in \omega$ such that no subset of $U$ of size $n$ is shattered by $E$. Otherwise, $E$ has infinite VC-dimension.
Next let me point out that for a bipartite graph $E\subseteq U\times V$,  "there is a largest $n$ such that all bipartite graphs $G\subseteq X\times Y$ with $|X|,|Y|<n$ can be embedded in $E$" is equivalent to the simpler statement "there is some finite bipartite graph which cannot be embedded in $E$".
So we want to show that $E$ has finite VC-dimension if and only if there is some finite bipartite graph which cannot be embedded in $E$. Equivalently, $E$ has infinite VC-dimension if and only if every finite bipartite graph can be embedded in $E$.
This is actually pretty straightforward, up to a wrinkle about extensionality.
$(\Leftarrow)$: Suppose every finite bipartite graph can be embedded in $E$. Let $n\in \omega$. Let $A$ be a set of size $n$, and consider the bipartite graph $G\subseteq A\times \mathcal{P}(A)$, with $G = \{(a,B)\mid a\in B\}$. Then there is an embedding of $G$ into $E$, i.e., injective functions $f\colon A\to U$ and $g\colon \mathcal{P}(A)\to V$ such that $aGB$ if and only if $f(a)Eg(B)$. Now $E$ shatters $f(A)$, since for $B\subseteq f(A)$, $f(A)\cap E_{g(f^{-1}(B))} = B$. Since $E$ shatters a set of every finite size, $E$ has infinite VC-dimension.
$(\Rightarrow)$: Suppose $E$ has infinite VC-dimension. Let $G\subseteq X\times Y$ be a finite bipartite graph. Note that we can extend $G$ to a finite extensional bipartite graph in the following way: For each $y\in Y$, add a new element $x_y$ to $X$, which is related by $E$ only to $y$. So we may assume $G$ is extensional. Let $n = |X|$. Since $E$ has infinite VC-dimension, there is some set $A\subseteq U$ of size $n$ which is shattered by $E$. Let $f\colon X\to A$ be any bijection. Now for each $y\in Y$, there is some $v_y\in V$ such that $E_{v_y}\cap A = f(G_y)$. Defining $g(y) = v_y$ (which is one-to-one because $G$ is extensional), the maps $f\colon X\to U$ and $g\colon Y\to V$ gives an embedding of $G$ into $E$.
