# Triangle-free Graph is Regular

Suppose that $G$ is a triangle free simple $n$ vertex graph such that every pair of non-adjacent vertices has exactly $2$ neighbours in common.

$1>$ Prove that $G$ is regular (A graph is regular if degrees of all its vertices are same)

$2>$ Given that $G$ is regular of degree $k$ , prove that the number of vertices of graph $G$ is $1+{k+1\choose 2}$

Can someone help me even start?

• For the first, prove that for any two adjancent vertices $A$ and $B$ their neighbours are paired by edge connections and thus the degrees of $A$ and $B$ are the same. Then use connectedness of the graph. – Wolfram Feb 10 '17 at 20:04
• @Wolfram Can you please explain a bit more? I am a beginner so.. – Disha Ghandwani Feb 10 '17 at 20:12
• This looks like a too difficult problem for the beginner in combinatorics. Okay, I'll explain. – Wolfram Feb 10 '17 at 20:25

1) Suppose $A$ and $B$ are connected by the edge, $C_1, C_2,\cdots, C_l$ are neighbors of $A$ that are not $B$; $D_1, D_2,\cdots, D_m$ are neighbors of $B$ that are not $A$. Then let's see what the statement gives us. Firstly, none of $C_i$ is a neighbor of $B$, because otherwise $ABC_i$ is a triangle of edges, but $G$ is triangle-free. Similarly, none of $D_j$ is a neighbour of $A$.
Let us now look how $D_j$ and $C_i$ are connected by the edges. For any $i$ the vertices $C_i$ and $B$ are not connected, so they have two common neighbors. One of them is $A$. The other one must be one of $D_j$, because they are the only other neighbors of $B$. Thus, for any $i$: $C_i$ is connected with $D_j$ for some $j$. This $j$ is unique, otherwise $C_i$ and $B$ have at least 3 common neighbors, which is nonsense. Similarly, one can prove that any $D_j$ is connected with exactly one of $C_i$. But this all means that there is the same number of $C_i$ and $D_j$, so $A$ and $B$ have the same degree.
Now it is enough to see that then any two vertices have the same degree. If two vertices $A$ and $B$ are adjancent, we just proved that, and if not, they have a common neighbor $C$. $\deg A=\deg C=\deg B$.
2) For any pair of disconnected vertices $(A,B)$ let us call a pair of their two common neighbors $(C,D)$ the sibling for $(A,B)$. $(C,D)$ are also disconnected because $G$ is triangle-free, and their sibling is $(A,B)$. Thus, all disconnected pairs of vertices are split into sibling pairs of pairs $((A,B),(C,D))$. In particular, for any vertex $A$ the number of pairs $(C,D)$, formed by its neighbors (they are all disconnected by triangle-freedom), and the number of pairs $(A,B)$, where $B$ is not connected with $A$, are equal, because they are in one-to-one correspondence under sibling relation. Now denote the number of vertices by $n$ and write that equality: $${k\choose2}=n-k-1$$ From this 2) follows.