MathDB
Gcd of cycle lengths

Source: Bulgaria National Olympiad 2023 P1

April 8, 2023
combinatoricsgraph theorynumber theorygreatest common divisor

Problem Statement

Let GG be a graph on n≥6n\geq 6 vertices and every vertex is of degree at least 3. If C1,C2,…,CkC_{1}, C_{2}, \dots, C_{k} are all the cycles in GG, determine all possible values of gcd⁡(∣C1∣,∣C2∣,…,∣Ck∣)\gcd(|C_{1}|, |C_{2}|, \dots, |C_{k}|) where ∣C∣|C| denotes the number of vertices in the cycle CC.
Back to ProblemsView on AoPS