В пунктах А и В находится по автомобилю. Каждую минуту эти два автомобиля одновременно переезжают в какой-либо соседний пункт (пункты, соединённые отрезками, называют соседними). Докажите, что автомобили никогда не окажутся одновременно в одном пункте.
Выделим некоторые вершины графа, обведя их в кружочек. Изначально, один из автомобилей находится в выделенной вершине, а второй нет. Из выделенной вершины можно попасть только в невыделенную и наоборот (двудольный граф). Поэтому в одной вершине автомобили оказаться не могут.
