On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:

**Lemma 0:** For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are no edges between them and $G\setminus(U\cup W) $ has a Hamilton path.

**Proof**: We apply the following algorithm, mantaining a partition of $V(G)$ into subsets $U,W$ and a path $P$. Initialize $U=V(G)$, $W=\phi$, $P=\phi$.

At each stage of the algorithm do the following: If $|U|\leq|W|$, stop.

Otherwise, if $P$ is empty, move a vertex from $U$ to $P$. If $P$ is non-empty, let $v$ be it's endpoint. If $N(v)\cap U\neq \phi$, pick a vertex $u\in N(v)\cap U$ , and move it to $P$, otherwise ($N(v)\cap U=\phi$) move $v$ to $W$.

At any point of the algorithm there are no edges between $U$ and $W$, and the value $|U|-|W|$ decreases by exactly one on each step.

I'd like to have a similar result, but for directed graphs, something similar to:

**"Naive Tentative Lemma":** For every directed graph $D$, there exists two disjoint sets $U,W\subseteq V(D)$ of equal size, such that there are no edges between them and $D\setminus(U\cup W)$ has a Hamilton (directed) path.

**My approach**: Modifying the algorithm slightly, by on each step checking $N^{+}(v)\cap U$ instead of $N(v)\cap U$, we can get the following result:

**Lemma 1**:For every directed graph $D$, there exists two disjoint sets $U,W\subseteq V(D)$ of equal size, such that **$(U,W)$ form a directed pair** and $D\setminus(U\cup W)$ has a Hamilton (directed) path.

The fact that they now form a directed pair is an issue, and using the algorithm directly would yield a $P$ that is not a directed path, but $U$ and $W$ would indeed have no edges between them.

My idea would be to prove something along the lines of:

**"Realistic Tentative Lemma:"** For every directed graph $D$, there exists **three** disjoint sets $U,W,F\subseteq V(D)$, where $U$ and $W$ are of equal size, and $|F|\leq \gamma n$ for some small $\gamma$, such that there are no edges between $U$ and $W$ and $D∖(U\cup W \cup F)$ has a Hamilton (directed) path.

This can be hinted from the algorithm above, by checking $N^{+}(v)\cap U$ and $N^{-}(v)\cap U$ for each endpoint of the path $P$, doing the same as before if $N^{+}\cap U \neq \phi$, and checking $N^{-}(v)\cap U$ when $N^{+}(v)\cap U =\phi$, if the in-neighbourhood is also empty, we move $v$ to $W$, if it isn't we move $v$ to $F$.

I don't really know how i would go about bounding $|F|$, which i would like to be small, or if there's a more clever way to go about this, or maybe another algorithm that would net something similar to the **"Naive Tentative Lemma"** from the get-go.

Any help or reference is greatly appreciated!