Problem

Source: Brazil EGMO TST1 2023 #4

Tags: graph theory, counting, combinatorics



In the reality show Big Sister Brasil, it is said that there is a treta if two people are friends with each other and enemies with a third one. For audience purposes, the broadcaster wants a lot of tretas. If friendship and enmity are reciprocal relationships, given $n$ people, what is the maximum number of tretas?