In a country with $2015$ cities there is exactly one two-way flight between each city. The three flights made between three cities belong to at most two different airline companies. No matter how the flights are shared between some number of companies, if there is always a city in which $k$ flights belong to the same airline, what is the maximum value of $k$?
Problem
Source: Turkey TST 2015
Tags: Turkey, TST, 2015, combinatorics, graph theory
Transandantal
08.06.2015 18:47
We will solve for general $n$. Answer is $\lceil 2n/5 \rceil$. Example. Divide $n$ points into $5$ groups numbered from $1$ to $5$. Color all in-group edges with color $1$. Color all edges between groups $1-2, 2-3, 3-4, 4-5 ,5-1$ with color $2$. And lastly, color all remaining edges with color $3$. Clearly, this configuration satisfies our conditions and it is impossible to find more than $\lceil 2n/5 \rceil$ edges. Proof for $\lceil 2n/5 \rceil$ . We shall start with a key LEMMA. In every coloring of a complete graph with three colors that avoiding rainbow triangle , at least one of the color classes must be disconnected. ("Rainbow triangle" means a triangle whose edges are colored with three different colors.) This result goes back to a 1967 paper of Gallai. It is proved, as Lemma A, in the following paper: "Edge colorings of complete graphs without tricolored triangles", András Gyárfás, Gábor Simony, Journal of Graph Theory, 46, #3, pages 211–216, July 2004, doi: 10.1002/jgt.20001.$\Box$ Consider our graph $G$. If it is colored with at least three colors, from the lemma, we will have a color $c$ whose subgraph is disconnected. Denote the connected components of $c$ with $G_1, G_2, ...G_k$. Observation. For any $i, j \le k$, all edges between $G_i$ and $G_j$ are of same color. Proof. We will prove that all edges from a fixed $v \in G_i$ to all $w \in G_j$ are of same color. Considering that for all $v \in G_i$ and $v\in G_j$ analogously, will imply the desired result. Since $G_j$ is connected in regards to $c$, it will have spanning tree. For any two consecutive vertices $x$ and $y$ on this spanning tree, edges $vx$ and $vy$ must be of same color (otherwise consider triangle $vxy$). Now, if for any $m$ and $n \in G_j$ , $vm$ and $vn$ are of different colors, the path from $m$ to $n$ on spanning tree will give a contradiction. This proves our result.$\Box$ Now we may consider $G_1, G_2, ... G_k$ as single vertices in order to simplify our graph. Now we get rid of color $c$. Continuing in this manner, we can decrease the number of colors to $2$. If there are at least $5$ vertices now (each vertice is a group of initial vertices) the group $a$ with least vertices could have at most $\lfloor n/5 \rfloor$ vertices. In this case $\lceil 4n/5 \rceil$ edges from $a$ are distributed between two colors. Result follows. Other small cases $4$ and $3$ could analogously be solved. Q.E.D