On a planet there are $M$ countries and $N$ cities. There are two-way roads between some of the cities. It is given that: (1) In each county there are at least three cities; (2) For each country and each city in the country is connected by roads with at least half of the other cities in the countries; (3) Each city is connceted with exactly one other city ,that is not in its country; (4) There are at most two roads between cities from cities in two different countries; (5) If two countries contain less than $2M$ cities in total then there is a road between them. Prove that there is cycle of lenght at least $M+\frac{N}{2}$.
Problem
Source:
Tags: combinatorics, graph theory
17.04.2018 14:54
A transparent application of 2 theorems that guarantee existence of a hamiltonian cycle- Dirac's and Ore's thms. Consider the cities and roads inside any fixed country $a$ as a graph $G_a$. By the Dirac's theorem, using $(1)$ and $(2)$, it follows there exists a hamiltonian cycle in $G_a$. Let us contract each country at a point, thus obtaining a graph $G'$. Strictly speaking it's a multigraph, since it is posible any two vertices of $G'$ to be connected with more than $1$ edge (but no more than two edges, condition $(4)$). Delete those double edges, if exist, and denote the remaining graph again by $G'$. Using $(3)$ and $(5)$, it follows the sum of the degrees of any two not connected vertices in $G'$ is at least $M$, which is the number of all vertices in $G'$. Hence, by Ore's theorem, there exists a hamiltonian cycle $C$ in $G'$. Following that cycle $C$ (with length $M$) , the condition $(3)$ guarantees, that we enter and then leave any country, say $a$, at different cities, say $a_1$ and $a_2$. But since there is a cycle inside $a$, hence there is a path between $a_1$ and $a_2$ consisting of at least $|a|/2$ edges, where $|a|$ is the number of vertices/cities in $a$. In that way, we can "expand" the cycle $C$ inside each country, getting a larger cycle with length at least $M+\frac{N}{2}$.
17.04.2018 22:33
Very easy problem indeed.
19.04.2018 22:31
Yeah, it's easy if one knows some theory about Hamiltonian graphs. And yes, maybe at that level it's supposed to know that theory, but the point is, there is nothing creative other than applying those theorems. The problem is deliberately constructed to apply the mentioned facts. That's why so many constraints are imposed. Btw, do you know how many participants solved it? As far as I know,...very few of them?!
19.04.2018 23:41
dgrozev wrote: Yeah, it's easy if one knows some theory about Hamiltonian graphs. And yes, maybe at that level it's supposed to know that theory, but the point is, there is nothing creative other than applying those theorems. The problem is deliberately constructed to apply the mentioned facts. That's why so many constraints are imposed. Btw, do you know how many participants solved it? As far as I know,...very few of them?! I think it is not correct to use Dirac's theorem since every city is connected to at least half of the OTHER ones in its country. For instance if a country has 3 cities a Hamiltonian graph clearly does not have to exist. btw I am from Bulgaria and made the same mistake on the competition
20.04.2018 16:58
bananaman2 wrote: I think it is not correct to use Dirac's theorem since every city is connected to at least half of the OTHER ones in its country. For instance if a country has 3 cities a Hamiltonian graph clearly does not have to exist. Oh, I see, sorry, I didn't pay attention. But isn't it just a typo? I mean the word "OTHER" in (2) : "every city is connected to at least half of the OTHER cities in its country". I checked, it's the same also in the original text, but I doubt the problem is true given that condition. As I see, the official solution also goes along the same lines, they proved there is a cycle inside every country and there is a cycle among countries (if we contract each country). They used the Ore's theorem two times without mentioning it (proven as a separated lemma) Of course the Dirac's one is an easy corollary of the Ore's thm.
20.04.2018 20:51
I am not sure whether the problem is true or not but the official solution is (i think...). Still if it were the way you say it is I would have got 7/7 and not 6/7 idk.
20.04.2018 22:09
Is there any essential difference between the official solution and my solution here? I can't see any difference. If it were the meaning, the way it was actually written, you should have got 0/7, not 6/7. You could have asked about that point just after the competition. But anyway, it is a serious gaff by the author and the jury, since it makes the problem totally different and more difficult if of course that statement is still true. It could have prevented some more acurate contestants from solving it and thus be punished instead of being awarded. Btw, the problem was proposed by Ivan Landzhev.
16.09.2018 13:45
I agree with dgrozev. Problem is so unnatural. Students can't solve this in limited test time without Dirac or Ore's theorem, maybe.