MathDB
Cycles in a directed graph

Source: Bulgarian Spring Tournament 2023 9.4

March 25, 2023
combinatorics

Problem Statement

Given is a directed graph with 2828 vertices, such that there do not exist vertices u,vu, v, such that u→vu \rightarrow v and v→uv \rightarrow u. Every 1616 vertices form a directed cycle. Prove that among any 1717 vertices, we can choose 1515 which form a directed cycle.
Back to ProblemsView on AoPS