Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
What book is this, by the way? –  J. M. Nov 6 '11 at 5:29
1  
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

1 Answer 1

up vote 2 down vote accepted

As you rightly guessed, there is no such graph with 4 vertices. In any graph with the property you state, there's always somebody who's everybody's friend. Once you put that constraint on a 4 vertex graph, it follows fairly easily that no such graph exists.

For the assertion that I make, check Wikipedia: http://en.wikipedia.org/wiki/Friendship_graph.

Martin Aigner and Gunter Ziegler's book, "Proofs from the Book" has a beautiful and entertaining explanation of friends and politicians.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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