Distance 2 neighbors in a directed graph

Question

Consider a directed graph G in which there is exactly one edge between any two distinct vertices in G. Prove that there is a vertex in G that is in the distance-2 neighborhood of every other vertex in G. Assume that there are at least two vertices in G.

Answer 1

Proof by induction on $n$ the number of vertices: for $n = 2$ it is obvious. If the statement is true for $n = k$, we show it is true for $n = k+1$. In a graph with $n = k+1$ remove one of the vertices, say $v_{k+1}$, that has the maximum outdegree. Now in the remaining graph, there is a vertex $v^*$ that is in the distance-2 neighbourhood of every vertex in $\{v_1, v_2, \dots, v_k\} - \{v^*\}$. Now, again consider $v_{k+1}$, if $v_{k+1}u$ is an edge in this graph for any $u$ that has $v^*$ in distance-1 neighbourhood, then $v^*$ is in the distance-2 neighbourhood of every vertex including $v_{k+1}$. Otherwise, the outdegree of $v_{k+1}$ is smaller than $k -$ (#of vertices that have $v^*$ in distance-1 neighbourhood). Note that the outdegree of $v^*$ in this case is $k+1 -$ (#of vertices that has $v^*$ in distance-1 neighbourhood) which contradicts the fact that $v_{k+1}$ has maximum oudegree.