# Directed version of this lemma

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!