Объясните , что значит d в этих высказываниях:
, что для любого n ≥ 3 существует граф с n вершинами, в котором n-1
вершина имеют попарно различные степени, причем изолированных вершин нет.
(док-во)
если n = 2k, v = {v1, v2, v2k}, положим e = {(vi, vj) | i + j ≥ 2k + 1 ∧ 1 ≤ i ≤ k <
j ≤ 2k} ∪ {(vi, vj) | k + 1 ≤ i пусть d∈n 0 ≤ d ≤ k-1. по построению графа, deg (v2k-d) = 2k-d-1, deg (vd + 1) = d + 1. тогда
только вершины vk + 1 и vk имеют одинаковые степени: δ (vk + 1) = δ (vk) = k.
если n = 2k + 1, v = {v1, v2, v2k + 1}, положим e = {(vi, vj) | i + j ≥ 2k + 2 ∧ 1 ≤ i ≤
k + 1 пусть d∈n 0 ≤ d ≤ k-1. по построению графа, deg (v2k + 1-d) = 2k-d, deg (vk + 1) = k, deg (vd + 1) =
d + 1. опять только vk + 1 и vk имеют одинаковые степени: deg (vk + 1) = deg (vk) = k.