MathDB
Cycles in graphs

Source: Iran pre-preparation course examination 2011- P5

February 25, 2011
combinatorics proposedcombinatorics

Problem Statement

a) Prove that if GG is 22-connected, then it has a cycle with the length at least min⁡{n(G),2δ(G)}\min\{n(G),2\delta(G)\}. (10 points)
b) Prove that every 2k2k-regular graph with 4k+14k+1 vertices has a hamiltonian cycle. (10 points)
Back to ProblemsView on AoPS