I'm studying graph theory and I can't figure out how to solve this problem. I'm not pretty good at graphs and it's pretty hard for me to solve this kind of problems. I would highly appreciate if you can hit me up with some explanation. Thanks in advance!
Question: Is it true that every k-connected ($k>1$) graph which does not have a Hamiltonian cycle has a cycle that contains $k$ independent vertices and their neighbors? This is known to be true for $k = 2$ and $3$. For example, the graph to the right is 3-connected but not Hamiltonian. And the dotted cycle shown contains $3$ independent vertices (the three vertices which are lighter in color) and thier neighbors. To see that it is not Hamiltonian, notice that this graph is just the complete bipartite graph $K(3,4)$.
Let's first think about the case when $G$ is connected. If $|V| < k$, then we certainly can't partition $V$ into $k$ non-empty subsets, so let's assume $|V| \geq k$.
I claim that in this case there is a suitable partition. To show this, it is enough to find a subset $V' \subseteq V$ with $|V'| = k-1$ such that $G - V'$ is connected: then we can take $V_1$ to be $V - V'$ and we can $V'$ into sets with one element each to get $V_2,\dots,V_k$. How do we find such a $V'$? Intuitively, we take a spanning tree of $G$ and "snap off" the leaves one by one until we have snapped of $k-1$. Formally, we can traverse $G$ according to some algorithm (e.g. DFS). Let $v_1, \dots, v_n$ be the order in which we visit the vertices during this traversal. The fact that we could traverse the vertices in this order shows that the first $n-(k-1)$ vertices induce a connected subgraph of $G$, so we can take $V'$ to be the last $k-1$ vertices.
What if $G$ is not connected? Well, if it has more connected components than $k$, then there cannot be such a partition (why?). Otherwise (provided that $|V| \geq k$) we can use essentially the same idea: take a spanning forest of $G$ and snap off leaves until the number of leaves snapped of plus the number of the remaining connected components is $k$. Again, this can be done by using a traversal order, only in this case it requires some thought to determine how many leaves we need to snap off.