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.



Bound for a sequence of vertices in a graph
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$.


