وجود و رسم گراف منتظم

گراف $k$-منتظم از مرتبهٔ $p$ جمع درجه‌هایش $kp$ است و این باید برابر $\mathrm{۲}q$، یعنی زوج باشد؛ پس اگر $kp$ فرد شد، چنین گرافی وجود ندارد. چون گراف ساده است، $k\le p-\mathrm{۱}$ است. برای کشیدن، یال‌ها را طوری بگذار که درجهٔ هر رأس دقیقاً $k$ شود: $k=p-\mathrm{۱}$ گراف کامل است، $k=\mathrm{۱}$ (برای $p$ زوج) رأس‌ها را دوتادوتا به هم وصل می‌کند و $k=\mathrm{۲}$ را با یک دور می‌سازی.