Bound for a sequence of vertices in a graph I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $e_v$ denote the union of $\{v\}$ and the end vertices of edges starting at $v$. I would like to assure that there are sequences of vertices $\{v_i\}_{i=1}^j$ and $\{v'_i\}_{i=1}^j$ for a graph $G$ such that $v_{i+1}\in S_i\cap e_{v'_{i+1}}$ where $S_0=G$ and $S_{i+1}=S_i\setminus e_{v'_{i+1}}$ with $$j\geq \frac{kn}{d}-C$$ for a constant $C>0$ that does not depend on the graph $G$. The problem would be to show that we can create sequences long enough. The constant $C$ depend only on $d$ and $k$ while the length of the sequences $j$ can vary for different graphs of this type.
I am only able to prove this for $k(k+1)\leq d$, but I do not think this is optimal. It is easy to see that for $k=1$ it is possible to have inequality with $d=1$ and $C=1$. I would like to know if there are similar theorems already proven or any insight that might help prove or disprove this conjecture.
 A: Let $q$ be a prime power and let $P$ be a projective plane of order $q$. It has $q^2+q+1$ points and $q^2+q+1$ lines. Each point lies on $q+1$ lines, and each line has $q+1$ points. Each pair of lines has exactly 1 common point. Since the point-line incidence graph is regular and bipartite, there is a bijection $L$ from points to lines such that $L(v)$ is a line through $v$ for every point $v$.
Now construct a graph $G$. The vertex set $V$ is the set of points of $P$. The out-neighbourhood of a vertex $v$ is $L(v)-v$, i.e. $e_v=L(v)$. So $n=q^2+q+1$ and $k=q$.
Now consider distinct $v'_1,\ldots,v'_{q+1}$. Since distinct lines have one common point, $|L(v'_1)\cup\cdots\cup L(v'_t)|\ge \sum_{i=1}^{q+1} (q-i+2)=\frac12(q+2)(q+3)>\frac12n+2q$. Thus, after $q+1=O(n^{1/2})$ steps, already less than half the vertices are available for the $\{v_i\}$ sequence. Even if all the remaining vertices can be chosen (most unlikely), in total less than half the vertices can be chosen.
I suspect the last part of this argument is unnecessarily weak and that the real bound is a lot smaller than $n/2$.
This example doesn't strictly violate the conjecture as stated since $C$ is allowed to be a function of $(k,d)$ which is a function of $n$.
