Bulgarian National Mathematical Olympiad

Consider a graph $G=(V,E)$ where the vertices are the towns and the edges are the roads. Denote the towns in the countries by $V_1,V_2,\dots ,V_M$. It follows from the condition of the problem that $$V=V_1\cup V_2\cup \cdots \cup V_M,V_i\cap V_j=\varnothing ,|V_i|\ge 3(1)$$ for all $i\ne j$. Moreover, any vertex is connected to at least half of the vertices from its own set (2), and to exactly one vertex from any other set (3). There are at most two edges between any two sets (4) and if for two sets $V_i$ and $V_j$ we have $|V_i|+|V_j|<2M$ then there exists at least one edge connecting a vertex from $V_i$

with vertex from $V_j$ (5). We have to prove that in $G$ there is a cycle of length at least $\frac{N}{2}+M$ (i.e. having at least $\frac{N}{2}+M$ vertices). We use the following Lemma. Lemma. Let $G=(V,E)$ be a graph with at least three vertices. If for any pair of vertices $u,v$ not connected by an edge we have $d(u)+d(v)\ge |V|$ then there is a cycle passing through all vertices. Denote by $G_i(V_i,E_i)$, $i=1,\dots ,M$, the subgraphs of $G$ induced by the sets $V_i$. In other words those are subgraphs having vertices from $V_i$ and edges – all edges from $G$ having both its ends in $V_i$. According to the Lemma for any these subgraphs there exists a cycle $C_i$ passing through all vertices of $V_i$. Define a new graph $H$ with vertices the sets $V_i$, $i=1,\dots ,M$. Two vertices $V_i$ and $V_j$ from $H$ are connected by an edge if there exist $x\in V_i$ and $y\in V_j$ connected by an edge in $G$, i.e. $xy\in E$. It is clear that $H$ has $M$ vertices and it follows from (3) that any vertex $V_i$ has degree $$d_H(V_i)\ge |V_i|,i=1,\dots ,M.$$ If $V_i$ and $V_j$ are not connected by an edge then $$d_H(V_i)+d_H(V_j)\ge \frac{1}{2}(|V_i|+|V_j|)\ge \frac{1}{2}\cdot 2M=M$$ and it follows from the Lemma that there is a cycle in $H$ passing through all $M$ vertices. Let this cycle by $V_1{V}_2\cdots V_M{V}_1$. It is clear that there are edges in $G$ $$x_{12}{x}_{12}^{+},\dots ,x_{i,i+1}^{-}{x}_{i,i+1}^{+},\dots ,x_{M,1}^{-}{x}_{M,1}^{+},$$ such that $x_{i,i+1}^{-}\in V_i$ и $x_{i,i+1}^{+}\in V_{i+1}$. Since any vertex $u\in V_i$ is connected to exactly one vertex outside $V_i$ we have that $x_{i-1,i}^{+}\ne x_{i,i+1}^{-}$, $x_{i-1,i}^{+},x_{i,i+1}^{-}\in V_i$ and all these vertices partition the cycle $C_i$ into two sections: $C_i^{\prime }$ and $C_i^{\prime \prime }$. We may assume that for any $i=1,\dots ,M$ the section $C_i^{\prime }$ includes at least half of the vertices from $V_i$. Consider the following cycle in $G$: $$x_{M,1}^{+}{C}_1^{\prime }{x}_{1,2}^{-}{x}_{1,2}^{+}{C}_2^{\prime }{x}_{2,3}^{-}\cdots x_{i-1,i}^{+}{C}_i^{\prime }{x}_{i,i+1}^{-}\cdots x_{M-1,M}^{+}{x}_{M-1,M}^{+}{C}_M^{\prime }{x}_{M,1}^{-}.$$ The number of edges (and vertices) in this cycle equals $$\sum _{i=1}^M\lceil \frac{|V_i|}{2}\rceil +1\ge \sum _{i=1}^M\frac{|V_i|}{2}+M=\frac{N}{2}+M,$$ which completes the proof.

Proof of the Lemma. Assume the statement is not true for a graph with $N\ge 3$ vertices. There exists a graph of $N$ vertices having the following properties: (1) $d(u)+d(v)\ge N$ for any pair of not adjacent vertices $u,v$; (2) a cycle through all the vertices does not exist. Without loss of generality assume that $G$ is maximal with the properties (1) and (2), i.e. adding an edge results in a cycle through all vertices. Since $G$ is not complete there exist a pair of vertices $u,v$ that are not adjacent. It follows from the maximality of $G$ that there exists a path from $u$ to $v$ through all vertices: $$u=x_1,x_2,\dots ,x_{N-1},x_N=v.$$ Let $S$ be the set of vertices adjacent to $v$ and $T$ the set of vertices adjacent to all vertices adjacent to $u$: $T=\{x_{i-1}|x_i$ adjacent to $u\}$. It follows from the condition of the Lemma that $S\cap T\ne \varnothing$. Let $x_j\in S\cap T$. It is clear that $$x_1,x_2,\dots ,x_j,x_N,x_{N-1},\dots ,x_{j+1},x_1$$ is a cycle through all the vertices, a contradiction to the initial assumption.