by @pypkaed & @krugarrr

1. Метод мат индукции

Метод мат. индукции — способ доказательства утверждений, зависящих от натурального аргумента.

Утверждение P(n), зависящее от натурального числа n, справедливо для любого n, если: а) P(1) является истинным утверждением б) P(n) остается истинным утверждением, если n увеличить на единицу, то и P(n+1) - истинное утверждение.

Метод мат. индукции предполагает два этапа:

1. Этап проверки: истинно ли P(1)
2. Этап доказательства: предполагается, что P(n) - истинно, и доказывается истинность P(n+1)

2. Грань планарного графа

Грань планарного графа - максимальный участок плоскости, такой, что любые точки этого участка могут быть соединены кривой, не пересекающей ребро графа.

Грань графа образуется минимальными циклами графа.

<aside> 💡 Количество граней графа вычисляется по формуле m - n + k + 1

</aside>

3. Необходимые условия планарности

Для любого связного планарного графа с v ≥ 3:

m ≤ 3n - 6

В любом планарном графе существует вершина, степень которой ≤ 5

Теорема Понтрягина-Куратовского:

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К5 или К3,3

4. Дерево (два определения)

Дерево — связный ациклический граф

Дерево — двудольный граф

Дерево — граф, любое ребро которого - мост

5. Граф блоков и точек сочленения