Exercise 7. Let G be an infinite directed graph, where every vertex has finite degree. We assume that, for each vertex $\mathrm{s}$, the in-degree of $s$ is strictly less than the out-degree of $s$. Let $v$ be a vertex of G. For any integer $n \geqslant 1$, we denote $V_{n}$ as the number of vertices that can be reached from $v$ by passing through at most $n$ edges, including $v$.

What is the smallest possible value of $V_{n}$?
Solution to Exercise 7 For any integer $n \geqslant 0$, we denote by $E_{n}$ the set of vertices reached by passing through $n$ edges of $G$ or fewer, and $F_{n}$ the set $E_{n} \backslash E_{n-1}$, i.e., the set of vertices reached by passing through $n$ edges of $G$ at a minimum. Furthermore, we denote by $a_{n}$ the number of edges $(x, y)$ such that $x, y \in E_{n}$, and $b_{n}$ the number of edges $(x, y)$ such that $x \in E_{n}$ and $y \notin E_{n}$. Note that these are exactly the edges $(x, y)$ such that $x \in F_{n}$ and $y \in F_{n+1}$.

By construction, we know that $a_{n}$ is less than or equal to the sum of the in-degrees of the vertices in $E_{n}$, while $a_{n}+b_{n}$ is equal to the sum of the out-degrees of the vertices in $E_{n}$. Therefore, we have $a_{n}+b_{n} \geqslant a_{n}+\left|E_{n}\right|$, so $b_{n} \geqslant\left|E_{n}\right|$. The pigeonhole principle then indicates that at least one of the vertices in $F_{n}$ has an out-degree of $b_{n} /\left|F_{n}\right|$ or more, so $\left|F_{n+1}\right| \geqslant b_{n} /\left|F_{n}\right| \geqslant\left|E_{n}\right| /\left|F_{n}\right|$. This shows in particular that

$$
\left|E_{n+2}\right|=\left|E_{n+1}\right|+\left|F_{n+2}\right| \geqslant\left|E_{n+1}\right|+\left|E_{n+1}\right| /\left|F_{n+1}\right|=\left|E_{n}\right|+\left|F_{n+1}\right|+\left(\left|E_{n}\right|+\left|F_{n+1}\right|\right) /\left|F_{n+1}\right| .
$$

The arithmetic-geometric mean inequality shows that $\left|F_{n+1}\right|+\left|E_{n}\right| /\left|F_{n+1}\right| \geqslant 2 \sqrt{\mid E_{n}}$, from which we deduce that $\left|E_{n+2}\right| \geqslant\left|E_{n}\right|+2 \sqrt{\left|E_{n}\right|}+1$.

We note that $\mathrm{E}_{0}=\mathrm{F}_{0}=\{v\}$, so $\left|\mathrm{E}_{0}\right|=\left|\mathrm{F}_{0}\right|=1$, and thus $\left|\mathrm{E}_{1}\right|=\left|\mathrm{E}_{0}\right|+\left|\mathrm{F}_{1}\right| \geqslant$ $1+\left|E_{0}\right| /\left|F_{0}\right|=2$. We then prove by induction on $n$ that $\left|E_{2 n}\right| \geqslant(n+1)^{2}$ and that $\left|E_{2 n+1}\right| \geqslant$ $(n+1)(n+2)$. First, this is true for $n=0$. Moreover, if these two equalities are true for an integer $n \geqslant 0$, then:

$\triangleright\left|E_{2 n+2}\right| \geqslant\left|E_{2 n}\right|+2 \sqrt{\left|E_{2 n}\right|}+1 \geqslant(n+1)^{2}+2(n+1)+1=(n+2)^{2} ;$

$\triangleright\left|E_{2 n+3}\right| \geqslant\left|E_{2 n+1}\right|+2 \sqrt{\left|E_{2 n+1}\right|}+1>(n+1)(n+2)+2(n+1)+1=(n+2)(n+3)-1$, so $\left|E_{2 n+3}\right| \geqslant(n+2)(n+3)$.

This concludes our induction.

Conversely, suppose that the vertices of the graph $\mathrm{G}$ are the pairs ( $\mathrm{a}, \mathrm{b}$ ) such that $0 \leqslant$ $2 \mathrm{~b} \leqslant \mathrm{a}$, and that the edges are the pairs $\left((\mathrm{a}, \mathrm{b}),\left(\mathrm{a}+1, \mathrm{~b}^{\prime}\right)\right.$ ). Then each vertex $(\mathrm{a}, \mathrm{b}$ ) has an in-degree of $\lceil\mathrm{a} / 2\rceil$ and an out-degree of $\lceil\mathrm{a} / 2\rceil+1$. Moreover, if $v$ is the vertex $(0,0)$, then $\mathrm{E}_{n}$ is the set of vertices $(a, b)$ such that $a \leqslant n$, which shows that $\left|E_{2 n}\right|=\sum_{k=0}^{n-1} 2(k+1)+$ $(n+1)=(n+1)^{2}$ and that $\left|E_{2 n+1}\right|=\left|E_{2 n}\right|+(n+1)=(n+1)(n+2)$.

Therefore, we can affirm that the smallest possible value of $V_{n}=\left|E_{n}\right|$ is $(n+2)^{2} / 4$ if $n$ is even, or $(n+1)(n+3) / 4$ if $n$ is odd, i.e., $\left\lfloor(n+2)^{2} / 4\right\rfloor$ in all cases.

![](https://cdn.mathpix.com/cropped/2024_06_04_dba72b67df798c080479g-08.jpg?height=347&width=1239&top_left_y=2065&top_left_x=454)