tournament $G=(V,E)$ property

127 Views Asked by At

Let $G=(V,E)$ be a tournament

For the definition of a tournament see here

Prove: There exists a vertex $v \in V$ such that there exists a path of length $\le2$ to every other vertex $w \in V$

Suppose that this is not true, then every vertex $v \in V$ has a vertex $w \in V$ it can only reach with more than $2$ edges.

I don't see how this would contradict tournament-property.

Would appreciate any help

2

There are 2 best solutions below

0
On

Let $d(v,u)$ be the distance from $v$ to $u,$ and let $$N(v)=|\{u\in V|d(v,u)\le2\}|$$ Let $v$ be a vertex such that $N(v)$ is maximal. If $N(v)=|V|$ we are done. Otherwise, there is a vertex $w\in V$ such that $d(v,w)>2$. If for some vertex $u$ there is an arc $vu,$ then there cannot be an arc $uw,$ for then there would be a path of length $2$ from $v$ to $w$. Since the graph is a tournament, there is an edge $wu,$ and so $u\ne v\implies d(w,u)\le d(v, u)$. That is, $N(w)\ge N(v)$. However, $d(v,w)>1\implies d(w,v)=1$ and $$N(w)>N(v),$$ contradicting the definition of $v$.

0
On

Let's call the vertices players; let's say that player $v$ beats player $w$ if there's an arc from $v$ to $w;$ and let's define the score (or outdegree) of player $v$ to be the number of players that $v$ beats.

Claim. If $v$ is any player with the maximum score, then there is a path of length $2$ from $v$ to any other player.

Proof. Let $w$ be any other player. If $w$ beats $v,$ and also beats everyone that $v$ beats, then $w$ has a greater score than $v,$ contradicting the assumption that $v$ has the maximum score. Therefore, either $w$ is beaten by $v$ (so there is a path of length $1$ from $v$ to $w$), or else $w$ is beaten by some player who is beaten by $v$ (so there is a path of length $2$ from $v$ to $w$).