Skip to main content
1 of 4
Masood
  • 169
  • 6

distribution of vertices in a turnoment

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