[Math] show that in a group of five people (where any two people are either friends or enemies)…

discrete mathematics

Show that in a group of five people (where any two people are either friends or enemies), there are not necessarily three mutual friends or three mutual enemies.

I am completely lost on this problem and have no idea where to even begin. Suggestions?

Best Answer

You can find the right configuration using this reasoning:

  • If one person $A$ in the group has (possibly more than) three friends $B,C,D$, then either some two of those three are also friends, completing a triangle of friends with $A$, or $B,C,D$ are a triangle of enemies. So we need each person to have at most two friends.
  • Analogously we get that each person must have at most two enemies; because there are five people, this means that each person has exactly two friends and two enemies.
  • Thinking of the people as nodes and their relationships as colored edges in a graph, as suggested in the other answers, we get that the edges of each color must form a union of cycles, but as we only have five nodes, this is only possible if they form two $5$-cycles.
Related Question