R xoliqovaning matematika kursini takrorlash fanidan mustaqilish I

2- teorema (Dirak). Uchlari soni uchtadan kam bo‘lmagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam bo‘lmasa, bu graf Gamilton grafi bo‘ladi.
Isboti³. Uchlari soni bo‘lgan graf berilgan bo‘lsin. Bu grafning istalgan uchi uchun shart bajarilsada, u Gamilton grafi 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 bilan belgilaymiz.
Yuqorida bayon qilingan usulni qo‘llash natijasida hosil bo‘lgan grafdagi uchlardan tashkil topgan ketma-ketlik biror Gamilton sikli bo‘lsin, bunda , – berilgan grafning uchlari, esa qo‘shib olingan uchlardan biri. Tushunarliki, uch uchga qo‘shni emas, aks holda siklni tuzishda uchni ishlatmasligimiz mumkin bo‘lar edi. Bu esa sonining minimalligiga ziddir.
Agar grafdagi uch uch bilan qo‘shni, uch esa uch bilan qo‘shni bo‘lsa, uch siklda uchdan bevosita keyingi uch bo‘la olmaydi, chunki bu holda siklni siklga almashtirish mumkin. Natijada hosil bo‘lgan grafning uchga qo‘shni bo‘lmagan uchlari soni uchga qo‘shni uchlari sonidan kichik emasligi (ya’ni bu son kamida ga teng ekanligi) ravshan. Boshqa tomondan esa hosil bo‘lgan grafning uchga qo‘shni uchlari soni kamida ga tengligi ko‘rinib turibdi. Hosil bo‘lgan grafning har bir uchi bir vaqtning o‘zida uchga qo‘shni ham, qo‘shnimas ham bo‘lishi mumkin emasligidan hosil bo‘lgan graf uchlarining umumiy soni ( ) ushbu sondan kichik emas, ya’ni . Oxirgi tengsizlik faqat bo‘lgandagina to‘g‘ridir. Bu esa shartiga ziddir. ■
D irak 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 ( ), har bir ( ) uchning darajasi 3ga teng: . Dirak teoremasidagi shart grafdagi hech qaysi uch uchun bajarilmasa ham, bu grafda ko‘rinishdagi Gamilton sikli bor bo‘lgani uchun u Gamilton grafidir.
1960 yilda O. Ore⁴ quyidagi teoremani isbotladi.