There are $2024$ cities in a country, every two of which are bidirectionally connected by exactly one of three modes of transportation - rail, air, or road. A tourist has arrived in this country and has the entire transportation scheme. He chooses a travel ticket for one of the modes of transportation and the city from which he starts his trip. He wants to visit as many cities as possible, but using only the ticket for the specified type of transportation. What is the largest $k$ for which the tourist will always be able to visit at least $k$ cities? During the route, he can return to the cities he has already visited. Proposed by Bogdan Rublov
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 11.8
Tags: combinatorics, graphs, graph theory
19.04.2023 16:32
The answer is $1012.$ So, we have a complete graph $K$ which edges are colored in 3 colors. We take the number of vertices of the maximum connected monochromatic subgraph. The question is to find the possible minimum of this value when we vary colors. The following claim has a standalone value. Claim. Let $K_{m,n}$ be a complete bipartite graph with parts of $m$ and $n$ vertices. Its edges are colored in two colors. Then there exists a connected subgraph with edges of the same color with at lest $(m+n)/2$ vertices. Proof. Let $A,B$ be the partitions of the vertices, $|A|=m, |B|=n$ and the colors be white and black. For any $a\in A,$ by $d_w(a)$ we denote the number of white edges incident with $a$ and $d_b(a)$ denotes the number of corresponding black edges. Suppose wlog $\sum_{a\in A}d_w(a)\ge \sum_{a\in A}d_b(a).$ It means $$\sum_{a\in A}d_w(a) \ge mn/2.$$We delete the black edges. Let the connected components of the remaining graph consist of $(m_1,n_1),(m_2,n_2),\dots,(m_k,n_k)$ vertices. Arguing by contradiction, assume $$m_i+n_i<\frac{m+n}{2} \qquad (1)$$We have $$\sum_{i=1}^k m_i n_i\ge \frac{mn}{2}$$It can be seen that under the conditions $(1)$ and $\sum_i m_i=m, \sum_i n_i=n$ it holds $$\sum_{i=1}^k m_i n_i< \frac{mn}{2}$$contradiction. $\square$ Back to the original problem. Let $K$ be a complete graph of order $4n, n\in\mathbb{N}.$ Take the largest possible monochromatic component, and its color be, say, white. Let $V$ be its vertex set. Assume $ |V|<2n.$ Let $V':=V(K)\setminus V.$ Consider the induced bipartite graph on the parts $V, V'.$ There is no edge between $V$ and $V'$ colored in white, because we took the maximum component. By the above claim, there is a connected monochrome subgraph with at least $4n/2=2n$ vertices, which contradicts the maximality of $V.$ It, remains to construct a coloring of $K_{4n}$ with maximum monochrome subgraph of exactly $2n$ vertices. Group the vertices in 4 groups $A_1,A_2,B_1,B_2,$ each of $n$ vertices. Color edges as follows: in white - those between $A_1$ and $A_2$ as well as between $B_1$ and $B_2;$ in black - between $A_1$ and $B_1$ and between $A_2$ and $B_2$; in red - between $A_1$ and $B_2$ and between $A_2$ and $B_1.$
19.11.2023 23:22
Here is an alternative proof of @dgrozev's lemma. By Pigeonhole, there is a collection of $e \geq \frac{mn}{2}$ edges of the same colour. We claim that the induced subgraph $H$ by this collection satisfies the requirements. It suffices to show that there exist vertices $a$ and $b$ with $\deg a + \deg b \geq \frac{m+n}{2}$, as then component formed by $a$, $b$ and their neighbours would satisfy the requirements. To do that, we will sum globally (i.e. throughout the whole graph) and rely on Pigeonhole. We have $\sum_{a\in A} \sum_{b\in B} (\deg a + \deg b) = |B| \sum_{a\in A} \deg a + |A| \sum_{b\in B} \deg b = |B| \cdot e + |A| \cdot e \geq \frac{mn}{2}(m+n)$. Since the number of pairs $(a,b)$ is $mn$, there is a pair with sum of degrees at least $\frac{m+n}{2}$, done!
20.11.2023 09:24
@above: Nice try! What you proved is that there exists a pair of vertices $(a,b)$ with $\deg(a) + \deg(b)\ge (m+n)/2$ which is next to trivial. What you have to prove is that there exists a pair $(a,b)$ connected with an edge such that $\deg(a) + \deg(b)\ge (m+n)/2$. Only then you can claim that $a$ and $b$ are in the same connected component. Fortunately, this idea can be carried out, but you need to sum $\deg(a) +\deg(b)$ over all edges.
20.11.2023 12:37
@dgrozev ooof, thanks a lot! Here is the fix along the approach you suggested, it took me some headaches to correct errors, but I agree it's easy. Similarly to before, we desire $\deg a + \deg b \geq \frac{m+n}{2}$ for an edge $ab$ and so we should sum globally over all edges and apply Pigeonhole. As usual, denote $V$ as the set of vertices and $E$ as the set of edges. We have $\sum_{ab \in E} (\deg a + \deg b) = \sum_{x \in V}(\deg x)^2$ since in the former sum each $\deg a$ is counted $\deg a$ times (as $a$ is incident with $\deg a$ edges). Now, $\sum_{x \in V}(\deg x)^2 = \sum_{a\in A}(\deg a)^2 + \sum_{b\in B}(\deg b)^2$ and by the inequality between Quadratic mean and Arithmetic mean this is at least $\frac{(\sum_{a\in A} \deg a)^2}{m} + \frac{(\sum_{b\in B} \deg b)^2}{n}$. The sums in both numerators equal the number of edges (note that the graph is bipartite) which is $e \geq \frac{mn}{2}$, so overall we have $\frac{e^2(m+n)}{mn}$ as a lower bound. Now by Pigeonhole there is an edge $ab$ with sum of degrees at least $\frac{e(m+n)}{mn} \geq \frac{m+n}{2}$, done!