Page 11 - 4336

У неорієнтованому графі без петель з n вершинами степінь

вершини може мати значення від 0 до n-1. Вершина степеня 0

називається ізольованою (вона не має інцидентних ребер та

суміжних вершин), а степеня 1 – кінцевою, або висячою (має

тільки одне інцидентне ребро). Якщо вершина має степінь n-1, то

вона суміжна з усіма іншими вершинами і у графі немає

ізольованих вершин. Аналогічно, якщо в графі є ізольована

вершина, то немає вершини степеня n-1 (суміжної з усіма

іншими). У графі з петлями, петля дає внесок у 2 одиниці в

степінь вершини.

Отже, справджуються наступні твердження для будь-якого

неорієнтованого графа без петель:

1. У будь-якому графі з n вершинами одночасно не можуть

існувати вершини степенів 0 і n-1.

2. У будь-якому графі з n вершинами (n≥2) є принаймні дві

вершини з однаковими степенями.

3. Сума степенів вершин графа G=(V, E) дорівнює подвоєній

кількості його ребер:

 (  v)  E2 . (1.1)
v V

Справедливість цього твердження випливає з того, що кожне

ребро графа інцидентне двом вершинам, тому у суму степенів

усіх вершин воно вносить дві одиниці.

4. Повний граф К з n вершинами має n(n-1)/2 ребер. Дійсно,
n
степінь кожної з n вершин дорівнює n-1, тому за формулою (1.1):

2 E    (v ) n ( n ) 1 , (1.2)

v V

звідки кількість ребер дорівнює:

E  n ( n 2 / ) 1 . (1.3)

11