Skip to main content
2 of 3
minor
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

For a 3-connected counterexample, you can take a 'truncated' Petersen graph, truncating meaning that we remplace each vertex of $Pete$ by a 'small' triangle (think of a truncated cube). Then an induced cycle $G[V_1]$ as above must hit each triangle and moreover alternate between triangle edges and edges of the original $Pete$. Thus the latter edges would form a Hamilton cycle of $Pete$, which doesn't exist.

Note that similar truncating constructions for higher connectivity $k>3$ won't work, as for $k=4$ a non Hamiltonian 4-regular 4-connected graph just doesn't exist (if my memory serves), and for $k>4$ a 'truncated vertex' $C_k$ might be visited more than once.

Wolfgang
  • 13.4k
  • 5
  • 45
  • 102