Spring 2017, problem 41
Let $G$ be a connected graph, with the degree of all vertices not less than $m \geq 3$ (that is the number of edges incoming to each vertex is not less than 3).
Assume further 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.$
This is maybe a hacky answer to this question.
Define our graph by G = (V,E). Then it's evident that |V| <= 3 will always contain a path such that every vertex is visited once.
Consider now the graph with 4 vertices. Then we must construct an edge set such that the degree of each vertex is greater than our equal to three, and such that there exists no path through all the vertices in G where every vertex is visited exactly once. Label our vertices V = [0,1,2,3]. Then the edge set E = [(0,1), (0,2), (0,3), (1,1), (2,2), (3,3)]. Then we have the degree of every vertex is exactly 3 (since loops count for 2), however there does not exist a path such that we can visit every vertex exactly once.