TEORI GRAF 7

Lemma Jabat Tangan

Jumlah derajat semua simpul pada suatu
graph adalah genap, yaitu dua kali jumlah
sisi pada graph tersebut.
Dengan kata lain, jika G = (V, E), maka

Lemma Jabat Tangan

                                                                        
Tinjau graph G1:
d(1) + d(2) + d(3) + d(4) =
2 + 3 + 3 + 2 = 10 =
2 x jumlah sisi = 2 x 5

Tinjau graph G2:
d(1) +d(2) + d(3)
= 3 + 3 + 4 = 10
= 2 x jumlah sisi = 2 x 5



Lemma Jabat Tangan

                                                     
Tinjau graph G3:
d(1) + d(2) + d(3) + d(4)
+ d(5)
=2+2+3+1+0
=8
=2 x jumlah sisi
=2 x 4


Lemma Jabat Tangan

Contoh:
Diketahui graph dengan lima buah simpul. Dapatkah kita
menggambar graph tersebut jika derajat masing-masing
simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya
ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya
genap
(2 + 3 + 3 + 4 + 4 = 16).