Why does a graph having a Hamiltonian cycle cannot break into more than k components if k>=1 vertices are removed?
Follow Math Help Forum on Facebook and Google+
Well, if you have a simple cycle with no other edges, then removing k vertices leaves at most k components. In an arbitrary graph with a Hamiltonian cycle, you have other edges, so the number of components cannot be higher.
View Tag Cloud