The following answer construct a tester for a graph being complete $\ell$-partite for a fixed value of $\ell$.
Consider the following tester:
- Choose $\ell+1$ vertices at random.
- Verify that the edges between them are consistent with a complete $\ell$-partite graph, that is, there is a way to color the vertices using $\ell$ colors such that there is an edge between two vertices iff they have different colors.
We claim that for every $\epsilon>0$ there exists $\delta>0$ such that if the test succeeds with probability at least $1-\delta$, then the graph is $\epsilon$-close to complete $\ell$-partite. To show this, we assume that the test succeeds with probability at least $1-\delta$, and show that the graph is $\epsilon(\delta)$-close to complete $\ell$-partite, where $\epsilon(\delta) \to 0$ as $\delta \to 0$. Moreover, the proof is by induction on $\delta$, the case $\ell = 1$ being trivial.
Let $\gamma$ be the probability that $\ell-1$ randomly chosen points form a clique. If $\gamma \leq \sqrt{\delta}$ then the graph passes the test for being complete $(\ell-2)$-partite with probability at least $1-\sqrt{\delta}-\delta$, and we complete the proof by induction. Assume, therefore, that $\gamma \ge \sqrt{\delta}$.
The expected failure probability of the test given that the first $\ell-1$ points form a clique is at most $\delta/\gamma \leq \sqrt{\delta}$. In particular, we can find a clique $x_1,\ldots,x_{\ell-1}$ such that with probability $1-\sqrt{\delta}$ over the choice of $x_\ell,x_{\ell+1}$, the graph induced by $x_1,\ldots,x_{\ell+1}$ is consistent with a complete $\ell$-partite graph.
Define the color $c(x)$ of a point $x \neq x_1,\ldots,x_{\ell-1}$ as follows. If $x$ is connected to all but $x_i$, then $c(x) = i$. If $x$ is connected to all, then $c(x) = \ell$. Otherwise, $c(x) = \bot$. Then with probability $1-\sqrt{\delta}$, the following holds:
- Either $c(x_\ell) = c(x_{\ell+1}) \neq \bot$ and $(x_\ell,x_{\ell+1})$ is not an edge,
- Or $c(x_\ell) \neq c(x_{\ell+1})$, $c(x_\ell),c(x_{\ell+1}) \neq \bot$, and $(x_\ell,x_{\ell+1})$ is an edge.
This shows that we can partition all but $\sqrt{\delta} n$ of the vertices into $\ell$ sets, such that the induced graph differs from the corresponding complete $\ell$-partite one in an $O(\sqrt{\delta})$-fraction of edges.