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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Wolfram Feb 10 '17 at 20:04
  • $\begingroup$ @Wolfram Can you please explain a bit more? I am a beginner so.. $\endgroup$ – Disha Ghandwani Feb 10 '17 at 20:12
  • $\begingroup$ This looks like a too difficult problem for the beginner in combinatorics. Okay, I'll explain. $\endgroup$ – 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.

  • $\begingroup$ What about the second part? $\endgroup$ – Disha Ghandwani Feb 11 '17 at 6:55
  • $\begingroup$ @DishaGhandwani added $\endgroup$ – Wolfram Feb 11 '17 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.