Skip to main content
4 of 4
Capitalized the title and added fraction in mathJax

Subset of the vertices in a tournament

Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|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