Showing that a graph is a union of cliques Consider an undirected graph $\mathbf{g}$ with $n$ vertices satisfying the property that two vertices are connected if and only if they have at least $k$ neighbors in common with $0<k<n-2$. In other words, letting $N_i(\mathbf{g})$ denote the neighborhood of $i$ (assuming that $i \notin N_i(\mathbf{g})$), we have:
$$ ij \in \mathbf{g} \iff |N_i(\mathbf{g}) \cap N_j(\mathbf{g})| \geq k. $$
Claim. $\mathbf{g}$ consists of a union of isolated nodes and distinct cliques with at least $k+2$ vertices, which overlap on at most $k-1$ vertices.
This observation has arisen from multiple simulation, but I am stuck trying to prove it rigorously. Any help (including pointers to relevant material) would be greatly appreciated.
It is clear that the overlaps between distinct cliques can have at most $k-1$ elements, otherwise the nodes in the two cliques would be connected. I am struggling to show, however, that any two connected nodes must belong to the same clique.
Edit. Here is an equivalent statement of the Claim.
Claim'. If $ij \in \mathbf{g}$, then there exists a complete subgraph $\mathbf{q} \subseteq (N_i(\mathbf{g}) \cap N_j(\mathbf{g})$ such that $|\mathbf{q}| \geq k$.
 A: The claim is true for $k=1$ and $k=2$. For $k=1$, the neighborhood condition immediately tells us that every edge is contained in a triangle. For $k=2$, if $vw$ is an edge, then $v$ and $w$ have common neighbors $x$ and $y$, giving us all the edges of a $4$-clique except $xy$. However, $x$ and $y$ have common neighbors $v$ and $w$, so $xy$ must also be an edge, and therefore each edge is contained in a $4$-clique.
For $k \ge 3$, there is a counterexample with $2k^2+k+2$ vertices, defined as follows.
Start with a complete bipartite graph $K_{2,k}$ with vertices $x_1, x_2$ on one side and vertices $y_1, \dots, y_k$ on the other side, and add the edge $x_1 x_2$ because $x_1$ and $x_2$ have $k$ common neighbors. To justify the existence of edges $x_i y_j$, for each such edge create a $k$-vertex clique $C(i,j)$ in which every vertex is also adjacent to both $x_i$ and to $y_j$.
To verify that this graph satisfies the neighborhood condition, we should check that there are no non-adjacent vertices with $k$ common neighbors:

*

*Vertices $y_i, y_j$ with $i \ne j$ only have two common neighbors: $x_1$ and $x_2$.

*A vertex $z \in C(i,j)$ has edges to $x_i$ and $y_j$, which are the only two common neighbors it can have with any vertex outside $C(i,j) \cup \{x_i, y_j\}$.

Finally, this graph is a counterexample to the claim because edge $x_1 x_2$ is not contained in any $(k+2)$-clique. In fact, it is not even contained in any $4$-clique: the common neighbors of $x_1$ and $x_2$ are exactly $y_1$ through $y_k$, which are an independent set.
A: The claim is false when $k\ge5$ and $n=\binom{k+2}2$.
Namely, suppose $k\ge5$, and let $G=L(K_{k+2})$, the line graph of the complete graph of order $k+2$.
$G$ is a graph of order $\binom{k+2}2$. Adjacent vertices of $G$ have exactly $k$ common neighbors, while distinct nonadjacent vertices have only $4$ common neighbors. The maximum cliques of $G$ have $k+1$ vertices, not $k+2$.
