# Sharing exactly one friend

My book has a problem: Describe a group of five people, any two of whom have exactly one friend in common. Can you find a group of four people with this same property?

I found such a group of five people (the graph looks like two triangles with one common vertex), and I'm fairly sure there is no such 4 vertex graph. However, I'm having trouble finding a more general explanation for my solution. Is there any way to categorize which n allow such a graph, and how you could construct it?

-
What book is this, by the way? – J. M. Nov 6 '11 at 5:29
Hint: Pick two vertices, lets call them 1,2. They have a common friend, label this vertex 3. Now, break the problem in 2 cases: $\{1,2\}$ is an edge, and $\{ 1,2 \}$ is not an edge.. In each case you know all edges among the first three vertices, completing the argument should be easy. – N. S. Nov 6 '11 at 5:36
The book is "Graph Theory" by Bondy and Murty – Carl Nov 6 '11 at 6:53