نکات و تعاریف

گراف کامل: گرافی که هر رأس آن با تمام رئوس دیگر مجاور باشد را گراف کامل می‌نامیم. گراف کامل n رأسی را با \(K_n \) نمایش می‌دهیم. می توان گفت \(K_n\) یک گراف \(n\) رأسی و \(n-1\)منتظم است.

گراف کامل \(p\) رأسی دارای \(\frac{p(p-1)}{2}\) یال است.

\[q(G)+q(\bar{G})=q(K_{n})\]

مکمل گراف کامل گراف تهی با همان تعداد رأس است.

مسیر: اگر \(u\) و \(v\) دو رأس از گراف \(G\) باشند، یک مسیر از \(u\) به \(v\) (یک  \(u-v\)مسیر) در \(G\) دنباله ای از رئوس دو‌به‌دو متمایز در \(G\) است که از \(u\) شروع و به \(v\) ختم می‌شود. به طوری که هر دو رأس متوالی این دنباله در \(G\) مجاور هم باشند. طول یک مسیر برابر است با تعداد یال‌های موجود در آن مسیر( یکی کمتر از تعداد رئوس موجود در آن مسیر). قرارداد می‌کنیم که دنباله متشکل از تنها یک رأس\(u\)، یک مسیر است با طول صفر از رأس \(u\) به خودش.

مثال: \(uwv\) یک \(u-v\) مسیر به طول 2 است.

گرافی را که تنها از یک مسیر \(n\) رأسی تشکیل شده باشد با \(P_n\) نمایش می‌دهیم.

مثال: گراف زیر \(P_5\) است.

دور: دنباله از رئوس دو‌به‌دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یک دور به طول \(n\) می‌نامیم. \(n\gt 2\)

گرافی را که تنها از یک دور \(n\) رأسی تشکیل شده باشد را با \(C_n \) نمایش می‌دهیم.

مثال: گراف زیر \(C_5 \) است.