Олимпиадные задачи из источника «9. Графы»

Несколько Совершенно Секретных Объектов соединены подземной железной дорогой таким образом, что каждый Объект напрямую соединён не более чем с тремя другими и от каждого Объекта можно добраться под землей до любого другого, сделав не более одной пересадки. Каково максимальное число Совершенно Секретных Объектов?

В Заитильщине 57 деревень, между некоторыми из которых проложены дороги. Известно, что из каждой деревни можно попасть в любую другую, притом по единственному маршруту.

  а) Докажите, что найдётся деревня, из которой выходит лишь одна дорога.

  б) Сколько дорог в Заитильщине?

Выписать в ряд цифры от 1 до 9 (каждую по разу) так, чтобы каждые две подряд идущие цифры давали бы двузначное число, делящееся на 7 или на 13.

Гуляя по Кенигсбергу, Леонард Эйлер захотел обойти город, пройдя по каждому мосту ровно один раз (см. рис.). Как ему это сделать? <div align="center"><img src="/storage/problem-media/32993/problem_32993_img_2.gif"></div>

Можно ли расположить на плоскости

  а) 4 точки так, чтобы каждая из них была соединена отрезками с тремя другими (без пересечений)?

  б) 6 точек и соединить их непересекающимися отрезками так, чтобы из каждой точки выходило ровно 4 отрезка?

Можно ли семь телефонов соединить проводами так, чтобы каждый телефон был соединён ровно с тремя?