MathDB

9.4

Part of 2023 Bulgarian Spring Mathematical Competition

Problems(1)

Cycles in a directed graph

Source: Bulgarian Spring Tournament 2023 9.4

3/25/2023
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.
combinatorics