Граф $ K_6 $ состоит из 6 вершин, каждая пара которых соединена ребром. Найдите наименьшую длину пути, проходящего по всем рёбрам этого графа. (напомним, что длина пути на 1 меньше количества вершин.)

Будем ориентировать граф по мере того, как будем проходить по ребрам. В конечном итоге получим
турнир на 6-ти вершинах.
Предположим, что наименьшая длина пути, проходящего по всем ребрам, равна 15. Тогда по каждому ребру прошли по одному разу. Сумма исходящих и входящих степеней каждой вершины равна
5. Рассмотрим вершину A, с которой не начинается путь длины 15. Т.к. суммарная степень этой вершины равна 5 и первое ребро в пути входит в вершину A (так.как начинали не с нее), то после обхода
всех ребер путь должен закончиться в вершине A (зашли, вышли, зашли, вышли, зашли). Тогда для
пяти вершин, с которых не начинался этот путь, верно утверждение, что путь должен закончиться
в этой вершине – противоречие. Тогда пути длины 15 быть не может.
Предположим, что существует путь длины 16. Тогда есть ребро, по которому прошли дважды, то
есть в конечном графе есть 2 вершины с суммарной степенью 6 и 4 вершины суммарной степенью
5. Аналогично предыдущему пункту, если путь не начинается в вершине A с нечетной степенью, то
он должен в ней закончится. Для графа на 16 ребрах есть по крайней мере 3 вершины нечетной степени, из которых не начинался пусть (есть 3 вершины, если начинали с вершины нечетной степени
и 4 вершины, если начинали с вершины четной степени). Тогда путь должен завершится хотя бы в
3-х вершинах – противоречие. Тогда пути 16 быть не может.
Приведем пример на путь длины 17. Пронумеруем вершины в графе цифрами от 1 до 6. Тогда искомый путь будет иметь вид: 1 – 3 – 6 – 4 – 2 – 5 – 4 – 1 – 5 – 6– 1 – 2 – 6 – 4 – 3 – 5 – 2 – 3, его длина – 17