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?

  • 1
    What book is this, by the way?2011-11-06
  • 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.2011-11-06
  • 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.