Skip to main content
2 of 4
edited title
Masood
  • 169
  • 6

subset of the vertices in a tournament

Suppose we have a complete directed graph. Can we always find a subset $S$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $|S|/2$ of the vertices in $S$? Note that $v$ can be in $S$. Also, we assume that each vertex has an incoming edge from itself.

Masood
  • 169
  • 6