MathDB
Independent sets

Source: Iran PPCE 2004

January 9, 2009
combinatorics proposedcombinatorics

Problem Statement

Let G G be a simple graph. Suppose that size of largest independent set in G G is α \alpha. Prove that: a) Vertices of G G can be partitioned to at most α \alpha paths. b) Suppose that a vertex and an edge are also cycles. Prove that vertices of G G can be partitioned to at most α \alpha cycles.
Back to ProblemsView on AoPS