3
$\begingroup$

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?

  • 0
    The book is "Graph Theory" by Bondy and Murty2011-11-06

1 Answers 1

2

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.