تعاریف و نکات

گراف همبند: گرافی که بین هر دو رأس آن حداقل یک مسیر باشد.

گراف ناهمبند: گرافی که همبند نباشد.

\[\sum_{I=1}^{p}{deg{\ v}_i=2q}\]

مجموع درجات رئوس یک گراف نمی‌تواند عددی فرد باشد.

تعداد رأس‌های فرد هر گراف، عددی زوج است.

اگر داشته باشیم \(\delta(G)\geq n\) گراف شامل یک مسیر به طول بزرگتر یا مساوی \(n\) است.

برای گراف هایی با تعداد رئوس فرد نمی‌توان گراف \(k\)- منتظمی رسم کرد که \(k\) فرد باشد.

تعداد یال‌های گراف \(n\) رأسی \(k\) منتظم برابر  \( \frac{kn}{2}\) است.