گراف مور

طول کوتاه ترین دور در یک گراف، کمر گراف نامیده می شود که با نماد (γ(G نشان داده می شود.به عنوان مثال مکعب کمر به طول ۴ دارد. برای گراف های kمنظم و با طول کمر ثابت معمولاً ویژگی های جالبی دارند.به عنوان مثال گراف G را یک گراف k منتظم با طول کمر ۴ چهار باشد اگرهر کدام از رأس های u گراف G را در نظر بگیریمk راس با فاصله یک از آن راس وجود دارد. از آنجا که گراف G هیچ مثلثی ندارد حداقل k-۱ راس با فاصله دو از u وجود دارند.
بنابراین داریم، G|≥۱+k+(k-۱)=۲k| و (|G| برابر با تعداد رئوس گراف است) فقط یک گراف با ویژگی G|=۲k| وجود داردو این و این همان گراف کامل دو بخشی Kk,k است. و حال اگر G گراف k منتظم با کمر پنج باشد و u هر یک از رئوس گراف باشد،k راس با فاصله یک از u وجود دارد به طوری که؛ G|≥۱+k+k(k-۱)=1+K۲|
گرافی است k منتظم با طول کمر پنج، به طوری که G|=K۲+۱| .فرض کنیم |n = |G . یک گراف ۱ منتظم نمی تواند کمر به طول ۵ داشته باشد. پس باید k≥۲ .اگر k =۲ پس n=۲۲+۱ = ۵ یعنی G یک دور به طول پنج دارد پس این تنها گراف مور با درجه ۲.
اگر k=۳ پس n=۳۲+۱=۱۰.