Графы. Как доказать?

Например, первая задача.

Полный граф, имеющий степень каждой вершины deg v = 3 — тетраэдр. Но у тетраэдра длина минимального цикла равна трём. Похоже, имеется ввиду планарный граф. По теореме Эйлера можно показать, что это планарный граф додекаэдра:

Если в графе все циклы минимальной длины 5, то по т. Эйлера: V − R + G = 2, где
V — число вершин
R — число рёбер
G — число граней
С учётом соотношения 3V = 2R (сумма степеней вершин равна удвоенному числу рёбер) .
В частности 2R = 5G ⇔ G = 3V/5. Имеем следующее уравнение:
V − 3V/2 + 3V/5 = 2 ⇔ V = 20.
Если полагать, что есть грани с длиной цикла более 5, то G = 3V/c < 3V/5, где с > 5 — а это уже большее значение корня для V в силу линейности по V. То есть, V = 20 — минимальное возможное значение.

1) лемма о рукопожатиях, 3п = 2ку. Теорема о связи числа ребер и длинны минимального цикла. Имеем п >= 20.
2) теорема о количестве ребер и следствие из нее
3) индукция. Бери самое маленькое дерево в базу, и шаги - 2 поддерева + новый корень
4) перебрать их все )