- Thread starter
- #1

#### cupofcoffee

##### New member

- Jun 5, 2013

- 7

Suppose not.

Consider a vertex . Let the set of its adjacent vertices be A and strangers be B. Clearly A has more than \(\displaystyle 2n/5\) members. As the graph is triangle free , there no mutual friends in A.

Consider B.

Assume there are two mutual friends p and q in B. As every member of B also has more than \(\displaystyle 2n/5\) adjacent vertices, A must have at least \(\displaystyle 4n/5 +2\) vertices, meaning that B has less than \(\displaystyle n/5\). Now, every member of A has more than \(\displaystyle 2n/5\) adjacent vertices outside A. But clearly this is not possible.

Is there a flaw in the above argument? I seems a little simplistic to me.