Tulip City (#117)

В городе Цветочном В площадей и Р улиц (Р ≥ В+1). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все исходящие из неё улицы. Докажите, что вначале можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.

Сложность: 5/10

Источник: Всероссийская олимпиада школьников по математике, 1994, 10 класс