Let $n$ and $k$ be positive integers, with $n\geq k+1$. There are $n$ countries on a planet, with some pairs of countries establishing diplomatic relations between them, such that each country has diplomatic relations with at least $k$ other countries. An evil villain wants to divide the countries, so he executes the following plan: (1) First, he selects two countries $A$ and $B$, and let them lead two allies, $\mathcal{A}$ and $\mathcal{B}$, respectively (so that $A\in \mathcal{A}$ and $B\in\mathcal{B}$). (2) Each other country individually decides wether it wants to join ally $\mathcal{A}$ or $\mathcal{B}$. (3) After all countries made their decisions, for any two countries with $X\in\mathcal{A}$ and $Y\in\mathcal{B}$, eliminate any diplomatic relations between them. Prove that, regardless of the initial diplomatic relations among the countries, the villain can always select two countries $A$ and $B$ so that, no matter how the countries choose their allies, there are at least $k$ diplomatic relations eliminated. Proposed by YaWNeeT.
Problem
Source: 2021 Taiwan TST Round 3 Mock Day 1 P3
Tags: graph theory, combinatorics, Taiwan
02.05.2021 09:06
Turns out that this is a direct consequence of the Gomory-Hu Algorithm. The key lemma in the proof (where it proves that min-cut can be "uncrossed") can also be used to directly solve this problem.
25.05.2021 18:43
Assign a capacity of $1$ to each edge in the obvious underlying graph. Pick a leaf in the Gomory-Hu tree of the graph. By a property of Gomory-Hu trees, the weight of the unique edge adjacent to the leaf is equal to the sum of capacities of the edges adjacent to this leaf, which is at least $k$. Therefore, the min-cut between the leaf and the vertex it is adjacent to, is at least $k$, as required.
25.05.2021 18:58
USJL wrote: Proposed by YaWNeeT. *Yawn* *Yeets paper out of earth* Cool name