4. Тип 11 № 7484 В графе 5 вершин, каждая из которых имеет индекс 4. Других вершин в этом графе нет. Сколько у него ребер?

Привет! Давай разберёмся с этим графом.

Что такое "индекс вершины"?

В контексте графов, "индекс вершины" часто означает степень вершины, то есть количество рёбер, которые в неё входят или из неё выходят. Если в задаче сказано, что каждая вершина имеет "индекс 4", это значит, что степень каждой вершины равна 4.

Дано:

• Количество вершин ($$n$$): 5
• Степень каждой вершины ($$k$$): 4

Найти: Количество рёбер ($$m$$).

Решение:

В теории графов существует важное правило, которое называется лемма о рукопожатиях. Она гласит, что сумма степеней всех вершин графа равна удвоенному количеству его рёбер. Математически это записывается так:

\[ \sum_{i=1}^{n} \text{deg}(v_i) = 2m \]

Где:

• $$n$$ — количество вершин.
• $$\text{deg}(v_i)$$ — степень $$i$$-й вершины.
• $$m$$ — количество рёбер.

В нашем случае:

• $$\text{deg}(v_i) = 4$$ для всех 5 вершин.
• Сумма степеней = 5 вершин * 4 (степень каждой вершины) = 20.

Теперь применяем лемму:

\[ 20 = 2m \]

Чтобы найти $$m$$, нужно разделить сумму степеней на 2:

\[ m = \frac{20}{2} = 10 \]

Ответ: 10