Some of the towns in a country are connected with bidirectional paths, where each town can be reached by any other by going through these paths. From each town there are at least $n \geq 3$ paths. In the country there is no such route that includes all towns exactly once. Find the least possible number of towns in this country (Answer depends from $n$).
Problem
Source: IX International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade
Tags: graph theory, combinatorics
24.09.2018 17:39
It's not difficult if one knows something about Hamiltonian cycles, especially the Dirac's theorem. The answer is $2n+2$. An example of graph with $2n+2$ vertices, each vertex has degree at least $n$, and without Hamiltonian path, is a bipartite graph $G=(A,B)$, $A$ has $n+2$ vertices, $B$ has $n$ vertices, all vertices of $A$ are connected wit all vertices of $B$ and there are no other edges. If there would exist a Hamiltonian path, it alternatively hits vertices of $A$ and $B$, and ultimately there would remain unhit vertex in $A$. Claim: Every graph $G$ with $m\leq 2n+1$ vertices, with minimal degree at least $n$, has a Hamiltonian path. If you know the idea behind the proof of the Dirac's theorem, it's exacly the same idea that does the job here. Take the maximal path $P=v_1v_2\dots v_k$ inside $G$ and for the sake of contradiction suppose $k< m $. Since $P$ is maximal, all vertices connected with $v_1$ and $v_k$ should lie inside $P$. By PHP there exist two consecutive vertices $v_i,v_{i+1}$ inside $P$, such that $v_1v_{i+1}$ and $v_iv_k$ are edges. Since $G$ is connected, there is a vertex $v_0$ outside $P$, connected with some vertex $v_j$ in $P$. Suppose $j\leq i$, the other case is similar. But then there is a bigger path than $P$, namely $v_0v_jv_{j+1}\dots v_i v_k v_{k-1}\dots v_{i+1}v_1v_2\dots v_{j-1}$, a contradiction. Comment: In the above argument, there is no need to require the graph to be connected, because it's connected anyway. If it is not, then one of its component would have been with the size at most $n$ and therefore not possible all degrees to be at least $n$. EDIT: The only thing that justifies the requirement the graph to be connected is perhaps to make it a bit more difficult to construct an example of a graph with $2n+2$ vertices that hasn't a Hamiltonian path. Otherwise that example is pretty easy - take two disconnected components, each a full graph with $n+1$ vertices.