$n$ regular graph with $2n$ vertices that doesn't contain triangle must be $K_{n\ n}$

Question

I am trying to prove that $n$ regular graph with $2n$ vertices that doesn't contain triangle must be $K_{n\ n}$(Complete bipartite graph). I have check for $n=1,2$ and need hint for proof for arbitrary $n$.

This is from last line of 809 page here http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Aigner808-816.pdf.

Answer 1

You need the graph to be triangle free, and this property is crucial since Calvin has already shown that the general case is false.

So suppose that $G(V,E)$ is a triangle-free $n$ regular graph with $2n$ vertices. Fix an arbitrary vertex $v$ and let $A$ denote the $n$ neighbors of $v$. Denote the remaining $n$ vertices (including $v$ itself) as $B$.

Since $v$ is connected to each vertex of $A$, it follows that no two vertices of $A$ can be connected for otherwise we will have a triangle. This means that the neighbors of each vertex in $A$ must fall within $B$. Moreover, since the graph is $n$ regular, it follows that the neighbors of each vertex in $A$ must be all of $B$. It follows that our graph is the complete bipartite graph $K_{n,n}$ with vertex partitions $A$ and $B$.

Answer 2

(This answer is for the previous version, which didn't state that the graph was triangle free.)

I don't think that is true. This is a 3 regular graph on 6 vertices that is not bi-partite (since it has a triangle).