MathDB

each cyle contains edges of both colors

Source: All-Russian 2007

May 4, 2007

inductionsymmetrycombinatorics unsolvedcombinatorics

Problem Statement

Given an undirected graph with

N

vertices. For any set of

k

vertices, where

1\le k\le N

, there are at most

2k-2

edges, which join vertices of this set. Prove that the edges may be coloured in two colours so that each cycle contains edges of both colours. (Graph may contain multiple edges). I. Bogdanov, G. Chelnokov

Back to Problems View on AoPS