Testing the property of being a union of three disjoint cliques
I will explain how to solve a similar question:


  Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of two disjoint cliques.


I assume that a clique is also considered a union of two disjoint cliques (one of them empty).

The natural test to try is


  Sample three vertices $x,y,z$, and check that the graph $G[x,y,z]$ induced by $x,y,z$ is either a triangle or an edge.


If a graph is a union of two disjoint cliques, then this test always passes. Conversely, suppose that this test always passes. Fix some vertex $x$, and let $V_1$ be the set of vertices connected to $x$, $V_2$ be the set of vertices not connected to $x$. If $y,z \in V_1$ then $G[x,y,z]$ includes the edges $(x,y),(x,z)$, and so must be a triangle, that is, $(y,z) \in E$. If $y,z \in V_2$ then $G[x,y,z]$ doesn't contain the edges $(x,y),(x,z)$, and so must be the edge $(y,z) \in E$. Finally, if $y \in V_1$ and $z \in V_2$ then $G[x,y,z]$ contains $(x,y)$ but not $(x,z)$. It must be an edge, so that $(y,z) \notin E$. We conclude that $G$ is indeed a union of two disjoint cliques.

Now suppose that the test passes with probability $1-\epsilon$. In particular, there must be a vertex $x_0$ such that conditioned on $x = x_0$, the test passes with probability at least $1-\epsilon$ (why?). Define $V_1,V_2$ as before. The argument above shows that $H$, the union of the cliques on $V_1$ and on $V_2$, is $\epsilon$-close to $G$ (in fact, slightly closer). Indeed, for every pair of vertices $y,z \neq x_0$, the test passes on $x_0,y,z$ if and only if the edge $(y,z)$ exists on both or neither $G$ and $H$. Thus $G$ and $H$ agree on all edges involving $x$, and agree on a $1-\epsilon$ fraction of the rest of the edges.



What about the actual question? Again, the natural test to try is


  Sample four vertices $x,y,z,w$, and check that the graph $G[x,y,z,w]$ induced by $x,y,z,w$ is a union of three disjoint cliques.


This time the analysis is slightly more complicated. Suppose that the test passes with probability $1 - \epsilon$. We consider two cases.

Case 1. $G$ contains at least a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, $G$ is $\sqrt{\epsilon}$-close to a clique.

Case 2. $G$ contains at most a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, we can find two unconnected vertices $x_0,y_0$ such that conditioned on $x=x_0,y=y_0$, the test passes with probability at least $1-\sqrt{\epsilon}$. We can now define $V_1,V_2,V_3$ analogously to how we defined $V_1,V_2$ in the preceding case, and show that $G$ is $\sqrt{\epsilon}$-close to the union of the cliques on $V_1,V_2,V_3$. Details left to the reader.