Question 154
A city has $M$ streets and $N$ squares, where $M$ and $N$ are positive integers such that $M \gt N$. Each street connects two squares and does not go through any other squares.
The citizens wish to change the appearance of the city. This year, each street will be coloured for the first time, in either red or blue. It is also determined that each subsequent year one square will be chosen and all the streets leading to that square will simultaneously change colour from blue to red and vice versa.
Prove that the citizens can choose the initial colours of streets so that it can never happen that all streets have the same colour.
(Russia 1994)
The citizens wish to change the appearance of the city. This year, each street will be coloured for the first time, in either red or blue. It is also determined that each subsequent year one square will be chosen and all the streets leading to that square will simultaneously change colour from blue to red and vice versa.
Prove that the citizens can choose the initial colours of streets so that it can never happen that all streets have the same colour.
(Russia 1994)