Question: consider an arbitrary connected graph g with n nodes what...
Consider an arbitrary connected graph 𝐺G with 𝑛n nodes. What is
the minimal number of edges do we have to add to 𝐺G in order to
guarantee that there exists a Hamiltonian cycle?
Now suppose 𝐺G has a simple path without repetition of vertices
with 𝑛n nodes. How many edges do you need to add?