Let $G=(V,E)$ be a directed graph.
We say that $w \in V$ is a child of $v \in V$ if $(v,w) \in E$. For $v \in V$, define the set of children of $v$ to be $$\mathcal{C}(v) := \{ w \in V \ | \ w \ \text{is a child of v} \},$$ and for a set $S \subseteq V$, define the set of children of $S$ to be $$\mathcal{C}(S) := \left (\bigcup_{v \in S} \mathcal{C}(v) \right) \setminus S.$$ We write $|\mathcal{C}(v)|$ (respectively $|\mathcal{C}(S)|$) for the number of children of $v$ (respectively $S$).
For $k \in \mathbb{N}$, we say that $G=(V,E)$ is $k$-dense if $\forall v \in V$ $|\mathcal{C}(v)| = 2$ and $\forall m \in \{ 2 , \dots k \}$ $\forall v_1,\dots,v_m \in V$ $|\mathcal{C}(\{ v_1 , \dots , v_m \})| \geq m$.
Hypothesis: There exists some $k \in \mathbb{N}$ such that every $k$-dense graph has strictly more than $2^{k+1}-1$ vertices.
NB: This question (also on MSE) proves that every $k$-dense graph has at least $2^{k+1}-1$ vertices, and mentions that this lower bound is likely not obtained for all but finitely-many $k \in \mathbb{N}$. I have not had time to work on an answer to the part of the problem given here, but it could possibly be solved with some straightforward computation so thought it worth writing down.
