Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
In a group of students, some pairs are friends. A teacher notices that no three students are all friends with each other. She wonders how many friendships there can be at most.
Prove Mantel's bound: a graph on vertices with no triangle has at most edges. Use a vertex of largest degree. Then find the largest number of friendships among the students and describe the friendship graph that reaches it.
A tree on vertices has edges; a forest with components has . Bipartite means no odd cycle; with no triangle, . A connected graph has an Euler circuit when all degrees are even, and an Euler trail when exactly two are odd.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. A vertex of largest degree. Let have degree , the largest. Its neighbours form a set .
Step 2. No edge inside . Two joined neighbours of would form a triangle with .
Step 3. Count edges. So every edge has at least one end in the other vertices. Each of those has degree at most . Hence .
Step 4. AM-GM. .
Step 5. Six students. . Split the students into two groups of and make every student a friend of each student in the other group. This is : friendships, and it is bipartite, so it has no triangle.
Answer: at most friendships, reached by . Proof complete.
Log in to join the discussion.
Loading…