Let $G$ be a simple graph with $2n$ vertices and $n^2$ edges. If $G$
has no triangles, then $G$ is the complete bipartite graph $K_{n,n}$.
I stumbled upon this proof for the result above, and I've failed to understand the following:
In the second paragraph of the proof, the user states: "[…] and the remaining $n-t$ vertices have degree $\leq n+t$", implying that each vertex in $V \setminus N(v)$ can only have neighbors in $N(v)$. I do see why each vertex in $N(v)$ can only have neighbours in $V \setminus N(v)$, but not the other way around. My understanding is that at this point in the proof, we haven't concluded yet that $V \setminus N(v)$ is an independent set (we do only in paragraph 3 after concluding that $G$ is $n$-regular), so it would be possible to have two adjacent vertices in $V \setminus N(v)$ without forming any triangles.
Any hints/clarifications will be greatly appreciated.
PS: I am aware this can be proved using Turan's theorem and the fact that $T(2n, 2) = K_{n, n}$, but I'm interested in this particular proof.
Best Answer
"implying that each vertex in $V\setminus N(v)$ can only have neighbours in $N(v)$"
No. The reason all vertices have degree $\le n+t$ is simply that $t$ was defined so that $n+t$ is equal to $\Delta(G)$, the maximum degree of $G$.