Introduction to Graph Theory · Problem 4.6

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · digraph-induced-acyclic-subdigraph

Problem

Let nn be a positive integer. Let DD be a digraph that has no cycles of length ≤2\leq 2. Assume that DD has at least 2n−12^{n-1} vertices. Prove that DD has an induced subdigraph that has nn vertices and has no cycles.

Browse the problem library