Qandaydir shartlarga bo'ysunuvchi graflarda Gamilton sikli mavjudligi haqida
bir necha tasdiqlar mavjud. Qator hollarda bu tasdiqlarning isbotlari konstraktiv
bo'lganligidan, Gamilton siklini tuzishga doir
samarali algoritmlar ham
yaratilgan.1952-yilda G. E. Dirak
1
quyidagi teoremani isbotladi.
2-teorema (Dirak). Uchlari soni uchtadan kam bo'lmagan grafdagi istalgan
uchning darajasi uchlar sonining yarmidan kam bo 'Imasa, bu graf Gamilton grafi
bo 'ladi.
Isboti
2
.
Uchlari soni
m >
3 bo'lgan graf berilgan bo'lsin. Bu
m
grafning istalgan v uchi uchun p(v)>—
shart bajarilsa-da, u
Gamilton graft bo'lmasin, deb faraz qilamiz.
Tabiiyki, istalgan grafga yetarlicha sondagi yangi uchlarni qo'shib olib, bu
uchlarning har birini grafdagi har bir uch bilan qirra orqali tutashtirsak,
berilgan
grafdan Gamilton grafini hosil qilish mumkin. Bu usul bilan berilgan grafdan
Gamilton grafini hosil qilish uchun qo'shilayotgan zarur uchlarning minimal sonini
к>
0 bilan belgilaymiz.
Yuqorida bayon qilingan usulni qo'llash natijasida hosil bo'lgan grafdagi
uchlardan
tashkil topgan
(v
v
w,v
2
,...,v^)
ketma-ketlikbiron Gamilton sikli bo'lsin,
bunda v,,v
2
— berilgan grafning uchlari,
w
esa qo'shib olingan uchlardan biri.
Tushunarliki, v
2
uch Vj uchga qo'shni emas, aks holda siklni tuzishda
w
uchni
ishlatmasUgimiz mumkin bo'lar edi. Bu esa
к
sonining minimalligiga ziddir.
Agar
grafdagi Vj uch
v
l
uch bilan qo'shni, v
2
uch esa v
2
uch bilan qo'shni bo'lsa, v
2
uch siklda Vj uchdan bevosita keyingi
uch bo'la olmaydi, chunki bu holda (v
1
,w,v
2
,...,v
1
,v
2
,..., v
x
) siklni
(v,,v
:
,...,v
2
,v
2
,...,Vj) siklga almashtirish mumkin. Natijada hosil bo'lgan grafning v
2
uchga qo'shni bo'lmagan
uchlari soni
v
x
uchga qo'shni uchlari sonidan
kichik
emasligi, ya'ni bu son kamida
ga teng ekanligi) ravshan. Boshqa tomondan esa hosilbo'lgan grafning v
2
uchga
qo'shni uchlari soni kamida
tengligi ko'rinib turibdi. Hosil bo'lgan grafning
har bir uchi bir vaqtning
o'zida v
2
uchga qo'shni ham, qo'shnimas ham bo'lishi mumkin emasligidan hosil
bo'lgan graf uchlarining umumiy soni
(m+k)
ushbu 2 у
+/с
1=
т+2к
sondan kichik
emas, ya'ni
m+k > m +2k.
Oxirgi tengsizlik faqat
k=0
bo'lgandagina to'g'ridir.
Bu esa k>0 shartiga ziddir. ■
Dirak teoremasi shartlari berilgan grafning Gamilton grafi
bo'lishi uchun yetarli, lekin ular zaruriy emas. Bu tasdiq to'g'ri
ekanligini 2-shaklda tasvirlangan graf misolida ko'ramiz. Bu
grafda sakkizta uch bo'lib (/и=8>3), har bir v (v = l,8) uchning
darajasi 3 ga teng:
