Existence of an $x,U$-fan in a $k$-connected graph

Question

Let $G$ be a $k$-connected graph. An $(x,U)$-fan is a set $U\subseteq V(G)$ of size $|U|\ge k$ together with a vertex $x\in V(G)\backslash U$ and a set of disjoint $(x,U)$-paths whose only common vertex is $x$. The number of disjoint $(x,U)$-paths is the size of the $(x,U)$-fan.

The problem is to show that in a $k$-connected graph there is always an $(x,U)$-fan of size $k$.

I was thinking induction over $k$, but the inductive step is rather messy.

[Edit:] Presumably, this question is asking to prove Dirac's fan lemma, which states that in a $k$-connected graph $G$, for every vertex $x$ and every $U \subseteq V(G)\setminus\{x\}$ with $|U| \geq k$, there is an $(x, U)$-fan of size $k$.

Answer 1

Applying Menger's Theorem, we know we have $k$ disjoint paths from $x$ to $y$ for any vertex pair $(x,y)$.

Now if we take any set $U \subseteq V(G)$ with $|U| \ge k$, and any vertex $x \in V(G) \setminus U$, we can construct an $(x,U)$-fan of size $k$ as follows:

1. First create a new vertex $y$ that is adjacent to every vertex in $U$. This new graph is still $k$-connected.
2. Now, applying Menger's theorem, we can find $k$ disjoint $(x,y)$-paths.
3. Removing $y$ from each of these paths leaves us with $k$ disjoint $(x,U)$-paths, that is, a $(x,U)$-fan of size $k$.

Answer 2

This is a consequence of the expansion lemma, which says that if you start with a $k$-connected graph $G$ and add a new vertex $v$ adjacent to at least $k$ vertices in $G$, the resulting graph $G+v$ is still $k$-connected. Plus Menger's theorem.

To find an $x,U$-fan using this strategy (for any $x$ and for any $U$ with $|U|\ge k$), add a vertex $y$ adjacent to all of $U$, and find $k$ internally disjoint $x,y$-paths. Then delete $y$ from all of them.

The expansion lemma can be proven just by thinking about vertex cuts in $G+v$. If we delete fewer than $k$ vertices, we do not disconnect $G$, and also we keep at least one neighbor of $v$.