Let $G$ be a $k$-connected graph $(k \geqslant 2)$. Let $v \in G$ and let $U \subset V(G) \backslash\{v\}$ with $|U| \geqslant k$. Show that $G$ contains $k$ paths from $v$ to $U$ with any two having only the vertex $v$ in common.

[No form of Menger's theorem or of the Max-Flow-Min-Cut theorem may be assumed without proof.]

Deduce that $G$ must contain a cycle of length at least $k$.

Suppose further that $G$ has no independent set of vertices of size $>k$. Show that $G$ is Hamiltonian.

[Hint. If not, let $C$ be a cycle of maximum length in $G$ and let $v \in V(G) \backslash V(C)$; consider the set of vertices on $C$ immediately preceding the endvertices of a collection of $k$ paths from $v$ to $C$ that have only the vertex $v$ in common.]