Mathematics — Graph Theory · digraph-induced-acyclic-subdigraph
Problem
Let n be a positive integer. Let D be a digraph that has no cycles of length ≤2. Assume that D has at least 2n−1 vertices. Prove that D has an induced subdigraph that has n vertices and has no cycles.