I have a question about the theorem of Gallai and Milgram stating that every directed graph $G$ has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the paths of $P$. (A path cover means a set of paths of $G$ such that each vertex of $G$ belongs to exactly one of these paths.)
More specifically I have a question related to the proof one can find in Diestel's graph theory book. The relevant part is pasted here for convenience.
I am having some trouble understanding the inductive step. The idea is to use induction to show that the path cover that minimizes the set of terminal vertices $\rm{ter}(\mathcal{P})$ will do the trick. If this is not the case, then one creates the graph $G'$ by removing from $G$ one specific vertex $v \in \rm{ter}(\mathcal{P})$
The idea is then that the path cover $\mathcal{P'}$ obtained by removing the end-vertex $v$ has a minimal set of terminal vertices among path covers of $G'.$
And here is where I get confused since it is assumed that if $\mathcal{P'}$ is not a path cover with minimal $\rm{ter}(P')$ then there is a path cover $\mathcal{P''}$ such that $\rm{ter}(\mathcal{P''}) \subset \rm{ter}(\mathcal{P'}).$
Why is this so? Can't it be that the terminal vertices of a "minimall" path cover in $G'$ is not a subset of $\rm{ter}(P')?$
I have reformulated the proof for your convenience.
To show: Every directed graph $G$ has a directed path cover $\mathcal P$ and an independent set $\{v_P \in V(G):: P \in \mathcal P\}$ of representatives of $\mathcal P$, that is, $\forall P \in \mathcal P: v_P \in V(P)$.
Proof: Note that the set of trivial directed paths is a directed path cover of size $|G|$.
We use induction on $|G|$ that for every directed path cover $\mathcal P = \{P_1,...,P_m\}$ with suitable $m \in \mathbb N$ and $ter(\mathcal P)$ minimal there is a set $\{v_P \in V(G):: P \in \mathcal P\}$ as claimed.
Case 1 ($|G|=1$): The claim is evident.
Case 2 ($|G|>1$): For $\ell \in \{1,...,m\}$ denote $v_\ell$ as the last vertex of $P_\ell$.
Case 2.1: If $m = 1$ or $ter(\mathcal P) = \{v_1,...,v_m\}$ is an independent set, then there is nothing more to show.
Case 2.2: Assume $m > 1$ and suppose without loss of generality that $G$ has an arc from $v_2$ to $v_1$, i.e., $ter(\mathcal P)$ is not independent. Since $P_2 v_2 v_1$ is again a directed path, the minimality of $ter(\mathcal P)$ implies that $v_1$ is not the only vertex of $P_1$.
Let $v \in V(P_1)$ be the vertex preceding $v_1$ on $P_1$, i.e., $v$ is the penultimate vertex in $P_1$. Then, $\mathcal P' := \{P_1 v, P_2, ..., P_m\}$ is a directed path cover of $G' := G - \{v_1\}$. Any independent set of representatives of $\mathcal P'$ in $G'$ will also work for $\mathcal P$ in $G$ if we can apply the induction hypothesis to $ter(\mathcal P') = \{v,v_2,...,v_m\}$ and $G'$, that is, we have to show that $ter(\mathcal P')$ is minimal among the sets of last vertices of directed path covers of $G'$.
Suppose that $G'$ has a directed path cover $\mathcal P''$ with $ter(\mathcal P'') \subsetneq ter(\mathcal P')$.
Case 2.2.1: If a directed path $P'' \in \mathcal P''$ ends in $v$, we may replace $P''$ in $\mathcal P''$ by $P'' v v_1$ to obtain a directed path cover of $G$ whose set of last vertices is a proper subset of $ter(\mathcal P)$ which is a contradiction to the choice of $\mathcal P$ above.
Case 2.2.2: No directed path in $\mathcal P''$ ends in $v$.
Case 2.2.2.1: If a directed path $P''' \in \mathcal P''$ ends in $v_2$, we similarly replace $P'''$ in $\mathcal P''$ by $P''' v_2 v_1$ to obtain again a contradicting directed path cover of $G$ as in case 2.2.1.
Case 2.2.2.2: If $ter(\mathcal P'') \subseteq \{v_3,...,v_m\}$, then $\mathcal P'' \cup \{v_1\}$ forms a directed path cover of $G$ that contradicts the minimality of $ter(\mathcal P)$ for the last time via the trivial path $v_1$.
Conclusion: Since $ter(\mathcal P')$ is minimal and $|G'| <|G|$, it follows by induction hypothesis that $G'$ has a suitable independent set $\{v_Q' \in V(G):: Q \in \mathcal P'\}$ which can be used also for $G$.