Prove that every nontrivial tournament has at least one serf.

Question

Serf definition: A vertex $z$ in a nontrivial tournament is called a serf if for every vertex $x$ distinct from $z$, either $x$ adjacent to $z$ or $x$ is adjacent to a vertex that is adjacent to $z$.

Prove that every nontrivial tournament has at least one serf.

I'm not sure if I understand this correctly, but a tournament is an oriented complete graph, and in a complete graph of order $n$ every vertex un-oriented adjacent to $n-1$ other vertex, so the only way for a vertex to not be a serf is that vertex has to be a source.

Assume the contrary that there exists a tournament that doesn't have any serf, then that tournament has every vertex is a source, which is impossible, thus every tournament must have at least one serf.

is my argument acceptable?

Answer 1

HINT: I’ll phrase this in terms of a real round-robin tournament rather than a graph. Let $p$ be a player with the smallest possible score, and let $B$ be the set of players beaten by $p$. Use the fact that every $b\in B$ has a score that is at least as big as $p$’s to show that every $b\in B$ beats someone who beats $p$. Thus, a player with minimal score must be a serf.

Answer 2

HINT: Consider the King Chicken theorem. This is almost the exact opposite of that theorem. The line of reasoning that proves one vertex must be a king chicken should also apply for a 'serf'. Recall that a 'King Chicken' dominates all vertices by a distance of at most 2. That is, if $u$ is a king chicken, then either $u$ beats all vertices, or for any vertex $v$, if $u$ does not dominate $v$, then $u$ dominates some vertex $x$ such that $x$ dominates $v$. I reiterate, a serf is the direct opposite of a king chicken. I hope that helps.