G is a simple undirected, connected graph with $\kappa$(G) < $\frac{n}{2}$. G has a simple path with 2$\kappa$(G) length.

Question

My question is just like above. We could first let the set S to be those minimum cutoff vertices $S=\{x|x\in\kappa(G)\}$. Then, we could divide S into some subsets. In the subsets, all elements are adjacent to some other elements. However, all elements are non-adjacent to different subsets. The length of shortest path required to connect two subsets is at least two. I think the most important part is to connect elements in same subsets. I want to claim that there exists a path connecting all of elements with 2#(S). I have discovered that each element in same subsets at least has degree of three. Otherwise, we could use smaller cutoff vertices to cut original graph. But, that certainly can't determine a simple path to connect them. If each vertex in same subsets are at least degree of four except for the elements connecting other subsets, then I could prove this question. However, I get stuck. Can someone give me some hints, thank you?

Answer 1

It looks similar to this lemma:
"If $G$ is a connected graph on $n$ vertices with minimum degree $\delta(G)<\frac{n}{2}$ then there exists a path of length $2\delta(G)$."

The proof of the lemma proceeds by considering a path $P$ of maximal length and uses the fact that the end vertices of $P$ have both degree at least $\delta(G)$. It is very similar to the proof of Dirac's theorem about hamiltonian graphs, maybe you've seen it. For a full proof, top of page 4: https://homepages.inf.ed.ac.uk/hguo/files/16.fall-adv.comb/Lecture_2_03.10.2016.pdf

For your problem, I think you can still consider a path of maximal length and prove that its end vertices must have degree at least $k(G)$ (why?), then the exact same proof should work.