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!
