## Task 2.

Let $n$ be a natural number. In a village, $2 n$ people live. Some of them are friends, and friendships are mutual. A perfect matching is a division of the village residents into $n$ pairs such that each pair consists of two people who are friends.

Assume that in the village there is exactly one perfect matching. What is the maximum possible number of friendships in the village?
## First Solution.

We identify people in the village with vertices and friendships with edges in a graph with $2 n$ vertices.

We claim that the answer is $n^{2}$.

First, we prove that it is possible to achieve exactly $n^{2}$ friendships in the village. Label the vertices $1,2, \ldots, 2 n$. Consider a graph where each vertex with an even label is connected to every vertex with a label smaller than its own, and these are the only edges. This graph has $2 n-1+$ $2 n-3+\ldots+3+1=n^{2}$ edges.

The matching $M$ given by $\{\{1,2\},\{3,4\}, \ldots,\{2 n-1,2 n\}\}$ is a perfect matching in this graph. Furthermore, notice that every perfect matching must include $\{2 n-1,2 n\}$ as a pair, since vertex $2 n-1$ has no other neighbors. Similarly, we conclude that $2 n-3$ must be paired with $2 n-2$ because its only remaining neighbor, $2 n$, is already paired. By the same logic, for every $k \leqslant n$, vertex $2 k-1$ must be paired with vertex $2 k$. Therefore, $M$ is the unique perfect matching in the graph.

Now, we prove that a graph with more than $n^{2}$ edges cannot have a unique perfect matching. Consider again a graph with vertices $1,2, \ldots, 2 n$, and assume that

$$
\{\{1,2\},\{3,4\}, \ldots,\{2 n-1,2 n\}\}
$$

is the only perfect matching in it.

Assume there are 3 edges between the sets $\{2 a-1,2 a\}$ and $\{2 b-1,2 b\}$ for some $1 \leqslant a<$ $b \leqslant n$. Then either $\{2 a-1,2 b-1\}$ and $\{2 a, 2 b\}$ are both edges in the graph, or $\{2 a-1,2 b\}$ and $\{2 a, 2 b-1\}$ are both edges in the graph. In either case, we get a different matching from the initial one by replacing the edges $\{2 a-1,2 a\}$ and $\{2 b-1,2 b\}$ with these edges, which is a contradiction. Therefore, there are at most two edges between $\{2 a-1,2 a\}$ and $\{2 b-1,2 b\}$.

Now, let's count the edges. We have $n$ edges within the perfect matching, and due to the previously proven claim, we have at most $2 \cdot \frac{n(n-1)}{2}$ edges outside the perfect matching. We conclude that there are at most $n^{2}$ edges in total.