Graflar nazariyasi haqida umumiy masha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg koyilishi va yechilishi graflar nazariyasining

Istalgan ikkita uchlari qolgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf graf deb ataladi. Uchlari soni ga teng bola graf bilan belgilanadi. Ravshanki, grafning qirralar soni bonalishda tutashtiruvchi faqat bittadan yoy mavjud bola orgraf deb ataladi. Ravshanki, tonalishlari bir-biriga qarama-qarshi bola orgraf hosil bola orgrafdagi yoylar soni oriyentirlanmagan topdir, yalgan toladi.



Agar grafning uchlariga qandaydir belgilar, masalan, sonlari mos qolsa, u belgilangan graf deb ataladi.






Agar va graflarning uchlari toni va toshnilik munosabatini saqlaydigan ornatish mumkin borifni quyidagicha ham ifodalash mumkin: agar va ularga mos bolsa, u holda va graflar izomorfdir. Agar izomorf graflardan biri oriyentirlangan bolishi va ulardagi mos yoylarning yolishlari shart.

Graf uchiga insident qirralar soni shu uchning lokal darajasi, yoki, qisqacha, darajasi, yoki valentligi deb ataladi. Grafdagi uchning darajasini bilan belgilaymiz.




Sirtmoqqa insident botiborga olish kerakki, qaralayotgan masalaga boglsa, u holda bunday graf darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki uch valentli) graf deb ataladi. graf nol darajali regulyar graf ekanligini, esa () darajali regulyar graf ekanligini tarinib turibdiki, oriyentirlanmagan grafda barcha uchlar darajalarining yigladi, chunki qirralarni sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq oko haqida). Ixtiyoriy oriyentirlanmagan grafda barcha uchlar darajalari yigplamini oplamlarga (bolsaki, grafning ixtiyoriy qirrasi bu toplamdan olingan biror uch bilan tutashtiradigan bolakli graf (bixromatik yoki Kyonig grafi) deb ataladi. Tarinib turibdiki, ikki bolagidagi ixtiyoriy ikkita uchlar qola olmaydi. Biror bolgan tolakli graf yulduz deb ataladi.