# bulding a Hamilton circuit in a given graph

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.

any ideas?

## 2 Answers

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.

This is not an answer but only a visualization of Snufsan's idea.

There you have an example for $k = 3$. Do you see the Hamilton cycle?