A consequence of the fan lemma for graphs (a theorem of H. Perfect) Let $G$ Be a graph, $x$ a vertex of $G$ and $Y$ and $Z$ subsets of $V - \{x\}$ and $|Y| < |Z|$. Suppose there are fans from $x$ to $Y$ and from $x$ to $Z$. I want to show that there exist $z \in Z-Y$ such  that there is a fan from $x$ to $Y \cup \{z\}$.
So what is a fan? 
It is a family of internally disjoint ($x$, $Y$) (or ($x$, $Z$)) paths. We assume that every $y \in Y$ is reached.
So, to give a solution, we need to come up with a $z$, together with the internally disjoint paths. 
If $Y \subset Z$ it holds trivially. I want to use the fan lemma: For a $k$-connected graph, if $Y \subset V-\{x\}$ consists of at least $k$ vertices then there exists a $k$-fan from $x$ to $Y$. But in this case, we don't have a $k$.
Can somebody help me? 
 A: You probably can forget about using the fan lemma, at least not without some kind of graph transformation.
This problem does not require $G$ to be $k$-connected.
But don't worry, if a problem involves a fan, its solution does not necessarily involve the fan lemma.
I found an algorithmic proof, that even yields a stronger result than you are asking for.
If you ever find a non-algorithmic proof, please post it here.
First we declare our variables.
Let $P_1,\ldots,P_k$ be the paths in a fan from $x$ to $Y$
and let $Q_1,\ldots,Q_l$ be the paths in a fan from $x$ to $Z$ ($k<l$).
Step 1: Mark all vertices of the $Q$-paths, except $x$.
Step 2: Color the last marked vertex on each $P$-path green ('last' in the sense: when walking
along the path starting at $x$). Note that a $P$-path need not have a green vertex at all.
Anyway, we end up with at most $k$ green vertices.
Step 3: If there is no $Q$-path with more than one green vertex, stop, otherwise continue with step 4.
Step 4: Choose a path $Q_i$ with more than one green vertex, and unmark
all vertices on this path after the first green vertex. Since the other green vertices
on $Q_i$ are no longer marked we must find a new green vertex on each of the involved
$P$-paths. The new green vertex still is the last marked vertex on this path (which again
may be absent).
Step 5: Continue at step 3.
At each iteration one or more of the green vertices either disappears or walks back
(along its $P$-path) in the direction of $x$, so this process must certainly end.
It can only end in a situation with at most one green vertex on any $Q$-path.
Without loss of generality (just by renumbering the paths)
we may assume that we find a green vertex $q_i$ on path $Q_i$ and path $P_i$
for $i=1,\ldots,m$ where $m\leq k <l$.
Now we are ready to build our final fan.
For $i=1,\ldots,m$ start at $x$, follow $Q_i$ until $q_i$ and from there walk to the end of path $P_i$.
For $i=m+1,\ldots,l$ we start at $x$ and follow $Q_i$ until its end.
This gives us a fan that involves all of $Y$ and $l-k$ vertices from $Z$.
This is a proper fan, because only the first part of each path used the marked vertices
and these are all disjoint because the first parts all belong to the original $x,Z$-fan.
The remainders of the paths do no use marked vertices anymore an they are disjoint
because they all belong to the original $x,Y$-fan.
Verify that this algorithm even works when $Y$ is a subset of $Z$ (although the solution
if finds is completely different from the 'trivial' solution you indicate in the question).
