3

Part of 2013 Tuymaada Olympiad

Problems(2)

Connected, not n-colourable graph

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

The vertices of a connected graph cannot be coloured with less than

n+1

colours (so that adjacent vertices have different colours). Prove that

\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.

inductionalgorithmgraph theorycombinatorics proposedcombinatorics

Inequality involving GM, QM, HM

Source: Tuymaada 2013, Day 1, Problem 3 Juniors

For every positive real numbers

a

b

prove the inequality

\displaystyle \sqrt{ab} \leq \dfrac{1}{3} \sqrt{\dfrac{a^2+b^2}{2}}+\dfrac{2}{3} \dfrac{2}{\dfrac{1}{a}+\dfrac{1}{b}}.

inequalitiesinequalities proposed