Подготовьте сообщение: а) «Задача о Кёнигсбергских мостах»; б) «Лемма о рукопожатиях».

а) Задача о Кёнигсбергских мостах

В старом Кёнигсберге семь мостов соединяли части города. Возник вопрос: можно ли пройти по каждому мосту ровно один раз и вернуться в исходное место. Леонард Эйлер представил части города вершинами графа, а мосты — его рёбрами. Он доказал, что такой маршрут невозможен: для замкнутого маршрута степени всех вершин должны быть чётными, а в графе Кёнигсберга таких вершин не было. Эта задача считается одним из первых примеров применения теории графов.

б) Лемма о рукопожатиях

Лемма утверждает: сумма степеней всех вершин конечного неориентированного графа равна удвоенному числу его рёбер:

\(\sum_{v\in V}d(v)=2|E|\).

Каждое ребро имеет два конца, поэтому при подсчёте степеней оно учитывается дважды. Следствие: число вершин нечётной степени в любом графе всегда чётно.