0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

This is not an answer but only a visualization of Snufsan's idea.enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.