2

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).

Barry Bush Jr.
  • 21

2 Answers2

2

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$.

Hana
  • 121
  • This looks like a very nice proof, but I started wondering why the contradiction argument would be valid. The proof structure doesn't seem to depend on the choice of $x$ being the vertex with the largest in-degree (it's not apparent to me at least), so the contradiction seems arbitrary. If you'd pick $x$ to be the vertex with the smallest in-degree for example, the same reasoning -independent of the degree of $x$- seems to apply, without the contradiction. – Fasermaler Sep 15 '15 at 08:08
  • 1
    $x$ has the largest in-degree guarantees that for all $y\in N^+(x)$ we can find at least one vertex $z\in N^-(x)$ such that $(y,z)$ is an edge. – Hana Sep 15 '15 at 18:36
  • Thanks for the clarification, I'll try to wrap my head around that :) – Fasermaler Sep 16 '15 at 15:50
1

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 (*).

user1001001
  • 5,143
  • 2
  • 22
  • 53
Leen Droogendijk
  • 7,456