1. To'plamlar, ularning berilish usullari va ular ustida amallar

1- t e o r e m a . Uchlari soni m va qirralari soni n bo‘lgan G graf uchun quyidagi tasdiqlar ekvivalentdir:

1. 
   G ^daraxtdir;
   

2. 
   G ^{asiklikdir va n  m 1;}
   

3. 
   G bog‘lamlidir va n  m 1;
   

4. 
   G bog‘lamlidir va undan istalgan qirrani olib tashlash amalini qo‘llash natijasida bog‘lamli bo‘lmagan graf hosil bo‘ladi, ya’ni G ning har bir qirrasi ko‘prikdir;
   
5. 
   G grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi;
   
6. 
   G asiklik bo‘lib, uning qo‘shni bo‘lmagan ikkita uchini qirra bilan tutashtirish amalini qo‘llash natijasida faqat bitta siklga ega bo‘lgan graf hosil bo‘ladi.
   

2-t e o r e m a . Istalgan daraxtning markazi uning bitta uchidan yoki ikkita qo‘shni uchlaridan iborat bo‘ladi.
3-t e o r e m a (Keli). Uchlari soni m bo‘lgan belgilangan daraxtlar soni
m^m2 ga teng.
41. Yo'naltirilgan graf.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar (yoylar) soni ga qarab belgilanadi va bu holda grafni -graf deb ataydilar.
Agar g(u,v) grafda kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanmagan) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan (oriyentirlangan) graf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb ataladi.

42.Yo'naltirilgan graf uchun qo'shnilik matrisasi.