Harvard-MIT Mathematics Tournament

Solution:

Each number be paired with each of the 9 other numbers, but each vertex can be used in at most 2 different pairs, so each number must occur on at least $\lceil 9 / 2\rceil=5$ different vertices. Thus, we need at least $10 \cdot 5=50$ vertices, so $n \geq 50$.

To see that $n=50$ is feasible, let the numbers $1, \ldots, 10$ be the vertices of a complete graph. Then each vertex has degree $9$, and there are $\binom{10}{2}=45$ edges. If we attach extra copies of the edges $1-2, 3-4, 5-6, 7-8$, and $9-10$, then every vertex will have degree $10$. In particular, the graph has an Eulerian tour, so we can follow this tour, successively numbering vertices of the $50$-gon according to the vertices of the graph we visit. Then, for each edge of the graph, there will be a corresponding edge of the polygon with the same two vertex labels on its endpoints. It follows that every pair of distinct numbers occurs at the endpoints of some edge of the polygon, and so $n=50$ is the answer.