Problem #WSP-000156

Problems Graph theory

Problem

There are \(n\) people at a royal ball. Every time three of them meet and talk, it turns out some two of them didn’t know each other before. Show that the maximum number of connections between the guests is \(\frac14 n^2\). If any guest \(A\) knows guest \(B\), then \(B\) knows \(A\), and this counts as one connection.