№2. Построй граф с 6 вершинами, каждая из которых соединена с тремя другими. Сколько рёбер в этом графе?

Решение:

В графе 6 вершин, и каждая вершина соединена с тремя другими. Это означает, что степень каждой вершины равна 3.

Согласно лемме о рукопожатиях (или основному свойству графов), сумма степеней всех вершин графа равна удвоенному числу его рёбер.

Пусть \( V \) — количество вершин, а \( E \) — количество рёбер.

Сумма степеней = \( \sum_{i=1}^{V} deg(v_i) \)

В данном случае, \( V = 6 \) и \( deg(v_i) = 3 \) для всех вершин.

Сумма степеней = \( 6 \times 3 = 18 \).

По лемме о рукопожатиях: \( \sum deg(v_i) = 2E \).

Значит, \( 18 = 2E \).

Разделим обе части на 2, чтобы найти количество рёбер:

\[ E = \frac{18}{2} = 9 \]

Таким образом, в графе 9 рёбер.

Ответ: 9 рёбер.