MathDB
Almost Hamiltonian path

Source: Ukrainian Mathematical Olympiad 2024. Day 2, Problem 10.8

March 20, 2024
graph theoryHamiltonian pathcombinatorics

Problem Statement

There are 20242024 cities in a country, some pairs of which are connected by bidirectional flights. For any distinct cities A,B,C,X,Y,ZA, B, C, X, Y, Z, it is possible to fly directly from some of the cities A,B,CA, B, C to some of the cities X,Y,ZX, Y, Z. Prove that it is possible to plan a route T1→T2→…→T2022T_1\to T_2 \to \ldots \to T_{2022} that passes through 20222022 distinct cities.
Proposed by Lior Shayn
Back to ProblemsView on AoPS