Let G be an undirected graph with k components. assume that every components consist a Hamilton circuit.
prove that by adding exactly k edges to the graph you can achieve a connected graph with Hamilton circuit.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
You just want to append the $k$ different hamiltonian circuits for the different components. So just order them in some order $P_1,...,P_k$ and let $u_i$ be the last vertex of the $i$th circuit and $v_i$ the first path of the $i$th circuit, and just add the edges $u_i - v_i+1$ for every $i < k$ and you'll get an hamiltonian circuit.