Задание по дискретной математике Докажите, что для любого натурального n существует неориентированный простой граф, в котором 2n вершин: по две вершины каждой степени k, 1≤k≤n.

Предыдущий
вопрос Следующий
вопрос

Для доказательства данного утверждения рассмотрим граф G = (V, E), где множество вершин V состоит из всех возможных пар вершин {vi, v_i'}, где i пробегает числа от 1 до n. То есть у нас будет n пар вершин {v1, v1'}, {v2, v2'}, ..., {vn, vn'}.

Теперь определим множество рёбер E следующим образом:

Для каждого i от 1 до n добавим ребро (vi v_i').Для каждого k от 1 до n добавим ребро (vk v_(k+1)') (при этом считаем (n+1)' = 1 в арифметике по модулю n).

Таким образом, у нас получился граф с 2n вершинами, и для каждой вершины степени k, 1≤k≤n, у нас есть две такие вершины в паре, соединенные ребром. По построению данного графа он является неориентированным и простым.

Таким образом, мы доказали, что для любого натурального числа n существует неориентированный простой граф с 2n вершинами, удовлетворяющий условию задачи.