Упр.102 ГДЗ Бунимович Булычев 10 класс (Алгебра)

1. Какое наибольшее число рёбер может быть у планарного графа с 5 вершинами? С 6 вершинами? Свои ответы обоснуйте.

Для планарного графа с числом вершин $$n \ge 3$$ выполняется неравенство

$$m \le 3n — 6,$$

где $$m$$ — число рёбер.

Тогда:

при $$n=5$$

$$m \le 3 \cdot 5 — 6 = 9,$$

при $$n=6$$

$$m \le 3 \cdot 6 — 6 = 12.$$

Следовательно, наибольшее число рёбер у планарного графа с 5 вершинами равно $$9$$, а с 6 вершинами — $$12$$.

Ответ

$$5$$ вершин — $$9$$ рёбер; $$6$$ вершин — $$12$$ рёбер.