Q1: A Completely Odd Cycle

Discrete Mathematics Level 5

I have \(n\) vertices, all of which are connected to each other by a single edge (diagram above is incomplete). Each edge is coloured in one of \(11\) colours.

As in usual graph theory, define a cycle to be a sequence of (unique) vertices, where each one is directly connected to the next, and where the start vertex is also the end vertex.

No matter how the edges are coloured, it is noticed that it is always possible to find a cycle of only one colour and with an odd number of vertices.

Find the minimum value of \(n\) for which this is true.

This problem is part of the set IMO Training: Set 1. Please read the introductory note; this has been adapted!)

Problem Loading...

Note Loading...

Set Loading...