Three travel companies provide transportation between $n$ cities, such that each connection between a pair of cities is covered by one company only. Prove that, for $n \geq 11$, there must exist a round-trip through some four cities, using the services of a same company, while for $n < 11$ this is not anymore necessarily true. Dan Schwarz
Problem
Source: Romanian TST 5 2007, Problem 3
Tags: inequalities, quadratics, combinatorics proposed, combinatorics
07.06.2007 16:59
For the first part : Since there are $\frac{n(n-1)}{2}$ connections, one company, say $A$ covers at least $\frac{n(n-1)}{6}$ connections. Let's consider the graph whose vertices are the $n$ cities and the edges are the travels covered by $A$. We have to prove that this graph contains a $C_{4}$. But it is a classical result (I'm quite sure to have proved it on this forum) that any graph with at least $\frac{n}{4}(1+\sqrt{4n-3})$ edges contains such a circuit. This gives the desired result for $n \geq 13$, and also for $n=11$ if we note that $\frac{n(n-1)}{6}$ can be replaced by $\frac{n(n-1)+4}{6}$ in that case, because the number of egdes has to be an integer. Pierre.
19.07.2007 12:31
pbornsztein wrote: For the first part : Since there are $ \frac{n(n-1)}{2}$ connections, one company, say $ A$ covers at least $ \frac{n(n-1)}{6}$ connections. Let's consider the graph whose vertices are the $ n$ cities and the edges are the travels covered by $ A$. We have to prove that this graph contains a $ C_{4}$. But it is a classical result (I'm quite sure to have proved it on this forum) that any graph with at least $ \frac{n}{4}(1+\sqrt{4n-3})$ edges contains such a circuit. This gives the desired result for $ n \geq 13$, and also for $ n=11$ if we note that $ \frac{n(n-1)}{6}$ can be replaced by $ \frac{n(n-1)+4}{6}$ in that case, because the number of egdes has to be an integer. Pierre. I cannot find your classical result on this forum. Where is it?
19.07.2007 14:29
It's in the "Proofs from the book". I can post it if you don't have it and you are interested.
19.07.2007 15:48
TomciO wrote: It's in the "Proofs from the book". I can post it if you don't have it and you are interested. I would very much appreciate that
19.07.2007 20:52
So, here you are, the proof was going something like that: Let $ d(i)$ be the number of neigbours of the vertex $ i$ and $ E$ the number of edges. We count all occurence of the type A-V-B for each vertex $ V$ (I mean, the triangles AVB without possibly the side AB). It's obvious that there are $ \sum \binom{d(i)}{2}$ of such occurences. On the other hand, for each pair A, B of vertices there is at most one other vertex adjacent to both of them, since there's not a $ C_{4}$ in the graph. So, the number of such occurences is not greater than number of all pair of vertices, in other words $ \sum \binom{d(i}{2}\leq \binom{n}{2}$. But: $ \sum \binom{d(i)}{2}= \frac{1}{2}\sum ((d(i))^{2}-d(i)) = \frac{1}{2}\sum d(i)^{2}-E \geq$ $ \frac{n}{2}(d(1)+...+d(n))^{2}-E = 2nE^{2}-E$ The second and the last comes from the fact that $ \sum d(i) = 2E$ and the inequality is an Arithmetic-Quadratic Mean Inequality. So we have the inequality: $ 2nE^{2}-E \leq \frac{n(n-1)}{2}$. After solving it in $ E$ we get the desired result.
17.11.2007 07:04
Hi, But seems that classical result does not solve this. We can only conclude that there exist a company own at least 19 lines. But for n=11,the classical result gives 20 which is larger than 19. I will be very appreciate someone can give a detailed solution of this problem (proof part)~~ Thanks, Yuncheng
05.01.2008 10:19
linyc wrote: Hi, But seems that classical result does not solve this. We can only conclude that there exist a company own at least 19 lines. But for n=11,the classical result gives 20 which is larger than 19. I will be very appreciate someone can give a detailed solution of this problem (proof part)~~ Thanks, Yuncheng Yeah, I think $ n=11,12$ still unsolved...
08.02.2008 15:27
Can somebody solve it?
24.02.2008 10:12
I think, $ n = 13$ also unsolved by Pierre's way. It creates equality, which is possible.
03.03.2008 09:31
Once again, anybody?
12.04.2009 09:22
I will only prove the case of n=11 For a positive integer n($ n \ge 4$), let $ e_{n}$ denote the maximal numbers of edges of a $ C_{4}$-free simple graph with n vertices. Lemma 0: $ e_{8}$=11, which is problem #5 of 7th CMO(China Mathematics Olympiad) in year 1992.So I won't prove this lemma.(in fact it isn't hard to prove) Lemma 1: $ e_{9}$=13. Proof of Lemma 1:First, if there is a $ C_{4}$-free simple graph with 9 vertices and 14 edges. Case 1: there exist a vertex whose degree is less than 3. Then delete this vertex and all the edges it belongs to, we get a $ C_{4}$-free simple graph with 8 vertices and at least 12 edges, which contradicts the Lemma 0; Case 2:every vertex's degree is at least 3. Because the sum of all degrees is 2*14=28, so the only possible case is that one vertex has a degree of 4 while all of other degrees are 3.Assume the special vertex is 1, and 1 has edges with vertex 2,3,4,5. If there is a vertex of 6,7,8,9 which has at least two edges to vertices 2,3,4,5, for example 6 has edges with vertex 2 and 3, then 1-2-6-3-1 is a $ C_{4}$, a contradiction.Otherwise vertices 6,7,8,9 all has at most one edge to vertices 2,3,4,5, which means vertices 6,7,8,9 each has at least two edges within themselves.And it is very easy to check there exists a $ C_{4}$ within vertices 6,7,8,9, a contradiction. Secondly if 9 vertices have the following 13 edges: 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9,9-1,1-3,3-5,5-7,7-9, then the 9-vertices,13-edges graph is $ C_{4}$-free. So Lemma 1 is proved. Lemma 2: $ e_{10}$=16. Proof of Lemma 2: First, if there is a $ C_{4}$-free simple graph with 10 vertices and 17 edges. Case 1: there exist a vertex whose degree is less than 4.Then delete this vertex and all the edges it belongs to, we get a $ C_{4}$-free simple graph with 9 vertices and at least 14 edges, which contradicts the Lemma 1; Case 2:every vertex's degree is at least 4. So the sum of all vertices is at least 40, but since there are only 17 edges, the sum should be 2*17=34, a contradiction, too. Secondly if 10 vertices have the following 16 edges:1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9,9-10,10-1,1-3,4-6,6-8,9-1,2-7 and 5-10, then the 10-vertices,16-edges graph is $ C_{4}$-free. So Lemma 2 is proved. Lemma 3: $ e_{11} \le 18$. Proof of Lemma 3: if there is a $ C_{4}$-free simple graph with 11 vertices and 19 edges. Case 1: there exist a vertex whose degree is less than 3. Then delete this vertex and all the edges it belongs to, we get a $ C_{4}$-free simple graph with 10 vertices and at least 17 edges, which contradicts the Lemma 2; Case 2:every vertex's degree is at least 3.Since the sum of all degrees is 2*19=38, and 38=3*11+5, so there are at most 5 vertices whose degree is greater than 3. Thus there are at least 6 vertices whose degree is 3.Assume they are 1,2,3,4,5,6 (1) There exist an edge within vertices 1,2,3,4,5,6, w.l.o.g assume it is edge 1-2.since the degree of 1 and 2 are both 3, there are at most 5 edges that vertex 1 or 2 belongs to. Then delete these 2 vertices and all the edges they belongs to, we get a $ C_{4}$-free simple graph with 9 vertices and at least 19-5=14 edges, which contradicts the Lemma 1; (2) There doesn't exist an edge within vertices 1,2,3,4,5,6. So each of these six vertices has 3 edges with vertices 7,8,9,10,11. For each pair of vertices of 7,8,9,10,11, if a vertex of 1,2,3,4,5,6 has both edges with them, for example 1-7,1-8, then call 7-1-8 an "angle". So each of these six vertices belongs to 3 angles, then there are 3*6=18 distinct angles in total. But there are only 10 distinct pairs of vertices among 7,8,9,10,11, according to the "pigeon-hole theorem",we get there exists a pair of vertices among 7,8,9,10,11 which belongs to at least 2 distinct angles, for example 7 and 8 belongs to angle 7-1-8 and 7-2-8, then there is a $ C_{4}$: 7-1-8-2-7, a contradiction, too. So Lemma 3 is proved. Now back to the original problem. There are 55 edges in a $ K_{11}$. Using three colors to color the 55 edges, we use the "pigeon-hole theorem" again we get there exist a color the number of whose edges are at least 55/3>18.i.e. there exists 19 edges of a same color. According to Lemma 3, there exists a $ C_{4}$ of the color. Q.E.D