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$ (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 are arrows from $C$ to $B$, we find a triangle. 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$, this gives two opposite edges if $n>2$.