Kvant Math Problem 987
Consider small instances to gain intuition.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m39s
Source on kvant.digital
Problem
A tournament involves $2m$ teams. In the first round, some $m$ pairs of teams played against each other, and in the second round, another $m$ pairs played. Prove that it is possible to select $m$ teams such that no two of them have played against each other.
M. Bona, high school student (Hungary)
Exploration
Consider small instances to gain intuition. For $m = 1$, there are $2$ teams, each pair plays once in the first and second rounds. Selecting $1$ team with no mutual opponent is trivial, as any single team suffices. For $m = 2$, there are $4$ teams. Suppose first-round matches are $(A,B)$ and $(C,D)$, second-round matches are $(A,C)$ and $(B,D)$. We can attempt to select $2$ teams with no mutual match. Choosing $B$ and $C$ works, as they did not play each other in either round. This suggests a general method may exist. Representing the tournament as a graph where vertices are teams and edges are matches, each round is a perfect matching. The problem reduces to selecting an independent set of size $m$ in the union of two perfect matchings on $2m$ vertices. The crucial difficulty is ensuring that no matter how the matchings are arranged, such an independent set exists.
Problem Understanding
We are asked to prove that in a $2m$-team tournament with two rounds of $m$ matches each, it is always possible to select $m$ teams such that no two have faced each other in either round. This is a Type A problem: a classification question, asserting existence for all configurations. The core difficulty is dealing with arbitrary pairings, which may seem to block large independent sets. Intuitively, since each team plays exactly twice, there are $2m$ edges total in a $2m$-vertex graph, which is sparse enough to allow an independent set of size $m$.
Proof Architecture
We model the tournament as a graph $G$ with $2m$ vertices, each representing a team. Edges correspond to matches; there are $m$ edges in the first round, $m$ edges in the second, forming a union of two perfect matchings.
Lemma 1: Any bipartite graph with equal bipartition $(X,Y)$ and a perfect matching from $X$ to $Y$ has a system of distinct representatives. Sketch: trivial by Hall's theorem; each vertex in $X$ is matched to a unique vertex in $Y$.
Lemma 2: In the union of two perfect matchings on $2m$ vertices, the graph decomposes into cycles of even length. Sketch: each vertex has degree $2$, so components are cycles; each cycle is even because the graph is 2-regular.
Lemma 3: In each even cycle, it is possible to select exactly half of the vertices forming an independent set. Sketch: choose alternating vertices along the cycle.
The hardest direction is justifying that the decomposition into cycles always produces even cycles; this is the step most prone to error.
Solution
Label the $2m$ teams as $1,2,\dots,2m$. Let $M_1$ and $M_2$ denote the sets of first-round and second-round matches, each a perfect matching of $m$ edges. Construct a graph $G$ with vertices $1,\dots,2m$ and edge set $M_1 \cup M_2$. Each vertex has degree $2$ because it participates in exactly one edge of $M_1$ and one edge of $M_2$. Therefore, $G$ is 2-regular, and every connected component of $G$ is a cycle.
We claim each cycle has even length. Let a cycle have length $k$. Each round contributes a perfect matching, so edges of $M_1$ alternate with edges of $M_2$ along the cycle. This alternation implies $k$ is divisible by $2$. Since all cycles are 2-regular, they are connected, and every cycle is composed of alternating edges from $M_1$ and $M_2$, so $k$ is even.
On each cycle, select every other vertex to form an independent set within that cycle. Since each cycle has even length, exactly half of its vertices are chosen, and no two are connected by an edge from either $M_1$ or $M_2$. Doing this for all cycles yields an independent set of exactly $m$ vertices.
This construction ensures that no two selected teams played against each other in either round. This completes the proof.
∎
Verification of Key Steps
To confirm that all cycles are even, consider a cycle in $G$ of length $k$. Walk along edges alternating between $M_1$ and $M_2$. Because each vertex contributes one edge to each matching, after traversing $k$ edges, one returns to the starting vertex, having alternated between the two matchings $k/2$ times each. Therefore, $k$ is divisible by $2$. Testing with small examples ($m=2$, $m=3$) confirms that cycles always consist of even numbers of vertices.
Choosing every other vertex on each even cycle produces an independent set: no two selected vertices are adjacent in the cycle, so no edge from $M_1$ or $M_2$ connects them. Small cycle examples verify this.
Alternative Approaches
One alternative is to use Hall's marriage theorem directly on a bipartite representation of the tournament, splitting vertices into two copies and connecting them to the teams they did not play against. This approach works but requires additional bookkeeping to ensure the bipartite graph has a perfect matching. The cycle decomposition method is more transparent, requires less auxiliary structure, and guarantees exactly $m$ teams can always be selected.