Is it true that any hamilton graph with "k" vertices has k/2 as the maximum independent set?

247 Views Asked by At

A Hamilton graph is a graph that has a Hamiltonian cycle ,which means a cycle exists in this graph in which you can visit every vertex of graph exactly once .

My observation is : - Say for a(any) Hamilton graph of 100 vertices , the value of its maximum independent set will be 50 .

Can somebody prove it or verify it ?

1

There are 1 best solutions below

4
On BEST ANSWER

This is plainly false. The complete graph on $n>2$ vertices is Hamiltonian but has maximum independent set size of only $1$.

However, if a Hamiltonian graph on $2n$ vertices is bipartite, then it is true that its maximum independent set size is $n$ (take one bipartition).