MathDB

8

Part of 2019 239 Open Mathematical Olympiad

Problems(2)

Correct coloring

Source: 239 2019 S8

7/31/2020
Given a natural number k>1k> 1. Prove that if through any edge of the graph GG passes less than [e(k−1)!−1][e(k-1)! - 1] simple cycles, then the vertices of this graph can be colored with kk colors in the correct way.
graph theorycombinatoricsChromatic numbercycles
Help the band with their instruments

Source: 239 2019 J8

7/31/2020
There are nn instruments in the laboratory, each two of them can be connected with a wire. Moreover, if four devices A,B,C,DA, B, C, D, are such that wires of ABAB, BCBC and CDCD are connected but there is no connected pair between CACA, ADAD and DBDB, a collapse occurs. A professor invented a wiring diagram that does not collapse. Coming to the laboratory, he found that the collapse has not yet occurred, but the devices are connected not according to his scheme. Prove that he can implement his scheme, each time connecting or disconnecting a pair of devices, so that the collapse won’t happen anytime.
combinatorics