62nd Ukrainian National Mathematical Olympiad

Consider this partition into pairs, denote the vertices $A_1,A_2,...,A_{2n}$ where the vertices $A_{2i-1},A_{2i}$ are connected by an edge for each $i$ from $1$ to $n$. Note that for every two pairs $(A_{2i-1},A_{2i})$, $(A_{2j-1},A_{2j})$, there are at most two edges between them: there cannot be two edges $(A_{2i-1},A_{2j-1})$, $(A_{2i},A_{2j})$, as then we could replace the chosen edges with these and still get a perfect pairing, and also the edges $(A_{2i-1},A_{2j})$, $(A_{2i},A_{2j-1})$. Thus, there can be no more than $n+2\cdot C_n^2=n^2$ edges in total.

The example looks like this: we draw all the edges of the form $(A_{2i-1},A_{2i})$, and also for each $i<j$ draw the edges $(A_{2i-1},A_{2j-1})$, $(A_{2i-1},A_{2j})$. Consider any perfect pairing in this graph. Notice that the vertex $A_2$ is connected only to $A_1$ so it must have an edge $(A_1,A_2)$. Among the remaining vertices, the vertex $A_4$ is connected only to $A_3$ so there must be an edge in the pairing $(A_3,A_4)$. Continuing similarly, all edges $(A_{2i-1},A_{2i})$ will be in this pairing.