Materi
Graf terdiri atas himpunan simpul (titik) dan himpunan sisi, dengan setiap sisi menghubungkan dua simpul. Dua simpul yang dihubungkan sebuah sisi disebut bertetangga. Graf dipakai untuk memodelkan apa pun yang berupa objek dan hubungan: kota dan jalan, komputer dan kabel, orang dan pertemanan, halaman web dan tautan. Derajat sebuah simpul adalah banyaknya sisi yang menyentuhnya. Simpul berderajat 0 tidak bertetangga dengan simpul mana pun.
Setiap sisi menambah derajat tepat dua simpul, yaitu kedua ujungnya. Akibatnya, jumlah derajat seluruh simpul selalu sama dengan dua kali banyak sisi. Hasil ini sering disebut lemma jabat tangan, dan punya akibat langsung: jumlah derajat selalu genap, sehingga banyaknya simpul berderajat ganjil juga selalu genap. Contoh: graf lima kota dengan derajat 3, 2, 2, 2, dan 1 punya jumlah derajat 10, jadi sisinya 10 ÷ 2 = 5. Di Python, graf kecil dapat disimpan sebagai daftar sisi, lalu derajatnya dihitung dengan menambah satu untuk kedua ujung setiap sisi.
jalan = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
derajat_c = sum(1 for u, v in jalan if "C" in (u, v))
print(derajat_c) # 3