A group consists of $n$ tourists. Among every three of them there are at least two that are not familiar. For any partition of the group into two busses, there are at least two familiar tourists in one bus. Prove that there is a tourist who is familiar with at most two fifth of all the tourists.
Problem
Source: MOP 2005 Homework - Black Group #12
Tags: graph theory, combinatorics unsolved, combinatorics
26.05.2014 20:06
We can translate the problem in graph theoretical terms. We have $G$ a graph without $K_3$'s, and with at least one cycle of odd length (larger than $3$). Now, we add edges until we can't add anymore edges, without creating a $K_3$ (we will always have an odd cycle, because adding edges to a non bipartite graph can't make it bipartite) (maybe we won't add any edge at all). If we manage to prove the problem for this new graph $G'$, the degree of the vertex found in $G'$ would be larger than (or equal) to the degree of the same vertex in $G$. Now, the key claim of the proof: Claim: We have a cycle of length $5$ in $G'$. Proof: Suppose this is not the case, then take the cycle with minimal odd length, suppose it has $2k+1$ edges with $k \ge 3$. Denote this cycle $A_1-A_2-\cdots -A_{2k+1}$. $A_1$ and $A_4$ are not connected, otherwise $A_1-A_4-A_5-\cdots -A_{2k+1}$ has lenth $2k-1$, impossible. Now, we have a vertex, say $K$ with $K$ connected to both $A_1$ and $A_4$ (otherwise, adding an edge between $A_1$ and $A_4$ doesn't create a $K_3$), so $A_1-A_2-A_3-A_4-K$ is a cycle of length $5<2k+1$, impossible. Now, denote the vertices of our $5$-cycle $B_1,\ldots,B_5$, with $b_i$ the degree of $B_i$. Because of obvious reasons, this cycle is an induced cycle ($B_i$ is connected to $B_j$ if and only if $|i-j|\equiv 1(mod 5)$). Take $X \neq B_i$ a vertex of our graph. $X$ can have at most $2$ neighbors in our cycle, so by a double counting argument $b_1+b_2+\cdots +b_5\le 2n-10+ 10$, so we have a $b_i \leq \frac{2}{5}n$, and we are done.
26.05.2014 22:47
MariusBocanu wrote: We have $G$ a graph without $K_3$'s, and with at least one cycle of odd length (larger than $3$). A little cryptic. In fact the second requirement translates in $G$ not being bipartite (as hinted at further on in the proof), and so the solver uses the known result that a graph is bipartite if and only if all its cycles are of even length, thus inferring the existence of an odd cycle of length larger than $3$. Nice proof otherwise (by saturating the graph). Let us also notice that the bound $\dfrac {2}{5}n$ cannot be improved, since for $G=C_5$ we get precisely that.