Graph Proof by induction.

Can you prove via induction that there exists a node in a directed graph of n nodes that can be reached in at most two edges from every other node in the graph. Every node in the graph is required to have an edge with every other node that either points out or in (For every pair of nodes X and Y, either X points to Y or Y points to X).

We call such a directed graph $T$ a tournament.

(Can't think of a proof using induction.)

Let $x$ be a vertex in $T$ with the largest in-degree. Let $N^+(x)=\{v\in V(T):(x,v)\in E(T)\}$ and $N^-(x)=\{v\in V(T):(v,x)\in E(T)\}$.

Let $y\in V(T)$ be any vertex other than $x$.

If $y\in N^-(x)$, then we are done since $(y,x)$ is an edge.

Now suppose $y\in N^+(x)$. It suffices to show that there exists $z\in N^-(x)$ so that $(y,z)$ is an edge, since than $y,z,x$ is a path of length 2 connecting $y$ and $x$. Indeed, if for all $z\in N^-(x)$, $(z,y)$ is an edge, then the in-degree of $y$ is at least one larger then that of $x$, contradicting the choice of $x$.

The graph you describe is called a tournament. The vertex you are looking for is called a king.

Here is a proof by induction (on the number $n$ of vertices). The induction base ($n=1$) is trivial.

For the induction step let $T$ be our tournament with $n>1$ vertices. Take an arbitrary vertex $v$ of $T$. By the induction hypothesis $T-v$ has a king $x$.

If there is a directed path from $x$ to $v$ of length at most 2, then $x$ is also a king in $T$ and we are done. So assume there is no such path (*). Then specifically the edge $xv$ is directed towards $v$.

We claim that $v$ is a king for $T$.

To see this let $y$ be any vertex of $T$ (different from $v$ and $x$) and assume there is no directed path from $y$ to $v$ of length at most $2$. Then edge $xy$ must be directed towards $y$ (or $yxv$ is such a forbidden path).

Since $x$ was a king in $T-v$, there must be a directed path $yzx$ from $y$ to $x$. Edge $vz$ must be directed towards $z$ (or $yzv$ is a forbidden path). But then $vzx$ is a path of length $2$ from $v$ to $x$, contradicting (*).