Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

Yechimi: G grafni yasab olamiz. Agar ikkita olim ingliz tilida yozishsa, bu
olimlar uchlarini yashil chiziq bilan birlashtiramiz, agar fransuz tilida yozishsa – 
qizil bilan, agar rus tilida yozishsa ko`k bilan. Shu tariqa biz to`liq K
17
grafini hosil 

qilamiz. Endi bu grafda uchlari olimlar bo`lgan va hamma uchta uchi bir hil rangda

bo`yalgan uchburchak hosil bo`lganini isbotlang.
4. Biron bir korxonada istalgan ikki tanishlar umumiy tanishga ega emas,
istalgan ikkita notanishning esa ikkita bir-birini taniydigan kishilari bor. Bu 
korxonada hamma ishchilarning bir hil sonda tanishlari borligini isbotlang.
Yechimi: Har bir ishchini G grafning uchi qilib olamiz. Bu masalada hamma
uchlarning darajasi bir hil ekanligini isbotlash kerak.


u va v o`zaro uchlari tutashgan graf bo`lsin. Masala shartiga binoan, u
1
, u

2
,…,u

n

uchlari u uch bilan o`zaro tutash va v uch bilan tutash bo`la olmaydi. Tutashmagan 

u
1
va v uchlarni ko`rib chiqamiz. Ular tutashgan u uchdan boshqa yana bir nuqtada 

uchrashishlari kerak, masalan v

1
da, shunda bu uch u uch bilan tutash bo`lmaydi. 

(1-rasm)

---

---

38

15.3- rasm 
Shu tariqa har bir i (2≤i≤p) ga shunday v

i

uch toplidaki, u u

i
va v uchlar bilan 
tutash lekin u bilan tutash bo`lmaydi. Shu sababli d(v)≥d(u). Shu kabi d(v)≤d(u) ni
isbotlasak bo`ladi. Demak, d(v)=d(u). (2-rasm) 
15.4-rasm 

5. Biron bir korxonada ma’lumki, istalgan ishchi shu korxonadagi oltita ishchi

bilan tanish. Oltita kishidan iborat guruhda bir ishchi qolgan barchasini taniydi. 
Korxonada nechta ishchi ishaydi.