Let $G=(V,E)$ be a graph with $|V|=n$ nodes, and the property for all pairs of nodes $a,b\in V, a\neq b$ we have precisely one edge, i.e. either $a\to b$ or $b\to a$.
This type of graph is called a tournament, as it depicts the outcome of a round-robin tournament of $n$ players.
I've tried myself at a algebraic-graph-theory proof that for all $n\ge 5$ we can construct a graph $G$ as above so that the maximum distance between any two nodes is 2.
(The regular proof brute-forces $n=1,..,6$ and finds that $n=3,5,6$ work, then uses induction to show that if we have a graph $G=(V,E)$ that works for $n$ , we can build one for $n+2$ by adding the vertices $v_1,v_2$ to it, and adding the edges $v_1→v_2$, and $v→v_1,v_2→v$ for all nodes $v\in V\setminus\{v_1,v_2\}$ )
Now to the algebraic-proof-theory proof on which I got stuck:
Let $L$ be the adjacency-matrix representation of $G$, then we find the following equality: $$ L + L^T +I= {1} $$ (where $1$ shall mean the matrix that has a $1$ in all cells$, and $I$ is the identity matrix)
We now have to show that all cells in $L^2 + L +I$ are $\ge 1$
(as $L$ is the adjacency matrix representation of $G$, $(L^k)_{i,j}$ tells us how many paths of length $k$ there are from node $i$ to node $j$)
We start by doing some algebraic transformations. Let $L_{\downarrow i}$ depict the $i$-th column of $L$. Then we have:
$$\begin{align} L^2 + L + I &= (1-L^T-I)L + L +I= (1-L^T)L + I \\ &= \pmatrix{1\\...\\1}(1,..,1)L - L^TL +I \\ &= \pmatrix{\sum L_{\downarrow1}& ...&\sum L_{\downarrow n} \\\vdots&\vdots&\vdots\\ \sum L_{\downarrow1}& ...&\sum L_{\downarrow n}} -L^T L +I \\ &= \pmatrix{\sum L_{\downarrow1}& ...&\sum L_{\downarrow n} \\\vdots&\vdots&\vdots\\ \sum L_{\downarrow1}& ...&\sum L_{\downarrow n}} - (L_{\downarrow i}^T L_{\downarrow j})_{i=1,...,n\\j=1,..,n}+I \\ &= \pmatrix{\sum L_{\downarrow1}- L_{\downarrow 1}^T L_{\downarrow 1}& ...&\sum L_{\downarrow n} - L_{\downarrow 1}^T L_{\downarrow n} \\\vdots&\vdots&\vdots\\ \sum L_{\downarrow1}- L_{\downarrow n}^T L_{\downarrow 1}& ...&\sum L_{\downarrow n} - L_{\downarrow n}^T L_{\downarrow n}} +I \end{align} $$
Our goal is to find a way to choose $L$ so that each cell is $\ge 1$.
For the diagonal we have $\sum L_{\downarrow i} - L_{\downarrow i}L_{\downarrow i} + 1 = 1\quad$ (with the $1$ coming from $I$).
So, if we can show that $\sum L_{\downarrow i} - L_{\downarrow i}L_{\downarrow j}\ge 1$ for all $j\neq i, j=1,..,n$, we are done.
We can rewrite each cell as: $$ \sum L_{\downarrow i} - L_{\downarrow i}^TL_{\downarrow j} \\= (1,...,1) L_{\downarrow i} - L_{\downarrow i}^TL_{\downarrow j} \\= \big((1,...,1) - L_{\downarrow i}^T \big)L_{\downarrow j} $$
This means that if we can choose the entries of $L$ so that for every ordered pair of columns of $L$ we have one row that is $0$ in the first, and $1$ in the second column, we are done.
(i.e. if the columns are $ L_{\downarrow i},L_{\downarrow j}, \,\, i,j\in\{1,..,n\}, i\neq j$ they'll have to look like $\pmatrix{...\\1\\...},\pmatrix{...\\0\\...}$ or equivalently $L_{k,i} = 1, L_{k,j} =0$)
And that's the point where I'm stuck. I can't think of a way that makes use of this property while also taking the special shape of $L$