Return to Revisions

For $n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, $b\to a$, take $i=j=a$, $k=b$. If not, consider a vertex $a$ with maximal indegree, it is at least $n-1$ (since all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there is an arrow $c\to b$ $C$ to $B$, we may take $i=c,j=a,k=b$. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$. It gives two opposite edges for $n>2$.