MathDB
Connected, not n-colourable graph

Source: Tuymaada 2013, Day 1, Problem 4 Juniors and 3 Seniors

July 20, 2013
inductionalgorithmgraph theorycombinatorics proposedcombinatorics

Problem Statement

The vertices of a connected graph cannot be coloured with less than n+1n+1 colours (so that adjacent vertices have different colours). Prove that n(n−1)2\dfrac{n(n-1)}{2} edges can be removed from the graph so that it remains connected.
V. Dolnikov
EDIT. It is confirmed by the official solution that the graph is tacitly assumed to be finite.
Back to ProblemsView on AoPS