Let $G$ be a connected graph, with degree of all vertices not less then $m \geq 3$, such that there is no path through all vertices of $G$ being in every vertex exactly once. Find the least possible number of vertices of $G.$
Problem
Source:
Tags: pigeonhole principle, graph theory, combinatorics proposed, combinatorics
23.01.2011 07:09
Maybe $2m+2$ is best possible. Consider the complete bipartite graph with $m$ vertices in one part, and $m+2$ in the other. Clearly it has no hamilton path as any such path alternates between with part it is in. I'll think more about this.
26.01.2011 06:08
Ok I think I have a proof that if we have $2m+1$ such vertices then it must contain a hamilton path: Let $v_1,v_2..v_L$ be a longest path that does not contain a vertex more than once, and suppose for contradiction that $L\leq 2m$. We will prove a lemma: Lemma: There exists a cycle consisting of exactly $v_1,v_2...v_L$ clearly $v_1$ and $v_L$ are joined only to a $v_i$ and no other vertex (otherwise we can extend our path to a longer path). If $v_1,v_L$ are adjacent then the lemma is proven, suppose it is not. An easy application of the pigeonhole principle shows that there exists an $1<i<L-1$ such that $v_i$ is connected to $v_L$ and $v_{i+1}$ is connected to $v_1$. Then we have a cycle: $v_1...v_i,v_L...v_{i+1}, v_1$. Now since our graph is connected and $L<2m+1$ some vertex $v_j$ is connected to some vertex $u$ not in our cycle. We now have a path with $L+1$ vertices if we start from $u$ and walk into the cycle, a contradiction.
27.12.2016 21:29
the answer is $2m+1$, the complete bipartite graph with sizes $m$ and $m+1$ is not hamiltonian as it does not have odd cycles. On the other hand, if the graph has $2m$ or less vertices it is hamiltonian by Dirac's theorem.