Every street in the city of Hamiltonville connects two squares, and every square may be reached by streets from every other. The governor discovered that if he closed all squares of any route not passing any square more than once, every remained square would be reachable from each other. Prove that there exists a circular route passing every square of the city exactly once. Author: S. Berlov
Problem
Source: Tuymaada 2008, Senior League, Second Day, Problem 5.
Tags: graph theory, combinatorics unsolved, combinatorics
20.07.2008 20:02
31.07.2008 18:24
Let's reformulate the problem on the "graph language": -Consider connected graph $ G$.About $ G$ it is known that if we delete any simple path(that doesn't pass any vertex more than once) new graph would still be connected. We need to prove that there exist a Hamiltonian cycle in $ G$, Solution: Obviosuly graph is not a tree,therefore it contains a cycle. Consider the cycle of a maximum length in $ G$,call it $ A = \{a_1,a_2,\dots,a_n\}$ and suppose to the contrary that $ n < |G|$. Let $ B$ be the set of all vertices that does not belong to $ A$,and by our assumption $ B$ is non-empty. Since $ G$ is connected there exist some vertex $ b\in B$ which is connected with at least one vertex from $ A$,WLOG assume that $ b$ is connected with $ a_1$.Now delete all the vertices of $ A$,except $ a_2$.There exist some path between $ a_2$ and $ b$,but then $ A$ is not the longest cycle,contradiction.
07.02.2018 07:59
that $n \ge 3$. By closing $v_2, v_3, \dots, v_{n-1}$, we see $v_1$ and $v_n$ are connected by a path not passing through $v_2, v_3, \dots, v_{n-1}$. Thus, there exists a cycle $v_1, v_2, \dots, v_n, \dots, v_1$. There cannot be vertices outside the cycle, otherwise we can extend our longest path, contradiction to maximality. Thus our cycle is Hamiltonian.