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.$

Comments

1 year ago

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.

1 year ago

Rats, iti didn't occur to me to use loops from a vertex to the same vertex. If those loops are not allowed is the answer 10? Thanks.

Post an answer:

To post an answer, please log in