There are $n$ cities on each side of Hung river, with two-way ferry routes between some pairs of cities across the river. A city is “convenient” if and only if the city has ferry routes to all cities on the other side. The river is “clear” if we can find $n$ different routes so that the end points of all these routes include all $2n$ cities. It is known that Hung river is currently unclear, but if we add any new route, then the river becomes clear. Determine all possible values for the number of convenient cities. Proposed by usjl
Problem
Source: 2023 Taiwan TST Round 1 Independent Study 2-C
Tags: graph theory, Taiwan, combinatorics
sn6dh
16.03.2023 09:39
Construct a graph whose vertices are cities and edges are ferry routes.
The answer is $n-1$.
Let $A, B$ be the set of the cities on the left side and the right side of Hung river, respectively.
Let $C, D$ be the set of convenient cities in $A, B$, respectively.
Let $N(V)$ denote the union of the neighbors of vertices in $V$.
By Hall Theorem: Hung river is clear $\iff\forall S\subseteq A,\ |N(S)|\geq|S|$.
Since Hung river is unclear, $\exists S\subseteq A$ s.t. $|N(S)|<|S|$.
Clearly, $S\subseteq A-C$.
If $S\neq A-C$, there exists $v\in A-C-S$.
Since $N(v)\subsetneq B$, after adding an edge from $v$ to $u\in B-N(v)$, $N(S)$ is still the same, and Hung river is still unclear, contradiction.
Therefore, $S=A-C$.
Since adding an edge will increase $|N(S)|$ by at most $1$, $|N(S)|=|S|-1$.
Since after adding an edge, $|N(S)|\geq|S|$, which should increase by at least $1$. We should not be able to add an edge between $S$ and $N(S)$, which means the induced graph from $S\cup N(S)$ is $K_{S, N(S)}$.
$\Rightarrow N(S)\subseteq D$ since all vertices in $N(S)$ should be connected to vertices in both $S(=A-C)$ and $C$.
On the other hand, $D\subseteq N(S)$ since every vertex in $D$ is connected to every vertex in $A$ including those in $S$.
$\therefore$ the number of convenient cities $=|C|+|D|=|C|+|N(S)|=|C|+|S|-1=|C|+|A-C|-1=|A|-1=n-1$.
PhilippineMonkey
16.03.2023 09:51
The answer is $\boxed{n-1}$.Just use Hall theorem. It's too easy for a TST exam.
USJL
16.03.2023 16:21
PhilippineMonkey wrote: The answer is $\boxed{n-1}$.Just use Hall theorem. It's too easy for a TST exam. I agree that this is an easy application of Hall's theorem. Is it too easy for TST though? I would believe that at least 1/3 of the 37 students this year did not solve this completely. People tend to underestimate the importance of easy problems in those team selection tests, especially in this case where there are 42 problems in total.
CrazyInMath
27.08.2023 10:02
Kőnig's Theorem
Assume that $k$ is a possible value, let's prove $k\geq n-1$.
Proof: Induct on $n$, base case is trivival ($k\geq 0$).
If $k<x-1$ won't work for $n=x$, that means adding one edge won't give a perfect matching. When $n=x+1$ we can find a subgraph with $x$ vertices with less than $x-1$ edges, so $k<x$ won't work for $n=x+1$.
Now we prove that $k=n-1$ works. The construction is a graph with a $K_{n,n-1}$ subgraph and a vertex with degree $0$.
Now we prove that $k\leq n-1$.
Proof: Assume $k>n-1$, if all convenient cities are on the same side, then the graph is $K_{n,n}$ which is not okay.
Now let the two sides have $\ell,m$ convenient cities each and $\ell+m>n-1$, and color them red and blue respectively. Now pick all red point on a side and all uncolored and some blue points on the other side, they form a $K_{\ell,\ell}$. The rest of the point form a $K_{n-\ell,n-\ell}$. Notice the size of the minimal vertex cover in the two subgraph is $\ell$ and $n-\ell$, respectively. Moreover, they does not intersect. So the original graph has a minimal vertex cover of size $n$, which means there's a perfect matching by Kőnig's.