فهرست برخی گراف های خاص

این مقاله به معرفی و بیان خواص برخی گراف های خاص می پردازد. این گراف ها شامل گراف هی وود، گراف پترسن، گراف کنزر، گراف های n - بعدی و ماز همپتون می باشند.
گراف هی وود یک گراف بدون جهت با14 رأس و 21 یال است .
گراف هی وود ۳ - منتظم است و این یعنی از هر راس آن سه یال بیرون آمده است، و همهٔ دورها در آن حداقل 6 و حد اکثر 14 یال دارد . عدد تقاطع گراف 3 است و کوچکترین گراف منتظم با این عدد تقاطع است. این گراف به نام پرسی جان هی وود نامگذاری شده است.
این گراف را هم به صورت دایره مانند می توان مشاهده نمود و هم به صورت بیضی مانند، در درون این گراف هر جفت از رأس هایش که به هم متصل اند در میانشان چهار راس وجود دارد و به تعداد راس هایش در داخل خود مثلث به وجود آورده است .
گراف پترسن یک گراف بدون جهت با ۱۰ رأس و ۱۵ یال است. گرافی کوچک که مثال و مثال نقض مفیدی برای خیلی از مسائل در نظریه گراف است. این گراف به جولیوس پترسن نسبت داده شده ولی در حقیقت برای اولین بار، ۱۲ سال زودتر در سال ۱۸۸۶ به وجود آمده بود.
گراف پترسن، گراف مکمل گراف خط K 5 است. همچنین گراف کنزر K G 5 , 2 است به این معنا که اگر برای هر کدام از زیرمجموعه های دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعه ها ی نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته می شود. گراف پترسن هم با گراف کامل K 5 و هم با گراف دوبخشی کامل K 3 , 3 همومورف است. متداول ترین شیوهٔ رسم گراف پترسن در یک صفحه، یک پنج ضلعی با یک ستارهٔ پنج رأسی درون آن است که هر یک از رأس های ستاره به رأس های پنج ضلعی با یک یال وصل می شود. این شیوهٔ نمایش متقارن است. در این شکل یال ها در ۵ نقطه یکدیگر را قطع می کنند. ( شکل۱ ) این روش ترسیم بهترین روش برای مینیمم کردن تعداد تقاطع ها نیست. روشی دیگر برای کشیدن گراف پترسن با دو نقطهٔ تقاطع وجود دارد که در شکل۲ نشان داده شده است. بنابراین عدد تقاطع گراف پترسن ۲ است. گراف پترسن همچنین می تواند در صفحه به گونه ای رسم شود که همهٔ یال ها طول یکسان برابر واحد داشته باشند. ( شکل۳ )
گراف پترسن مسیر هامیلتونی دارد ولی دور هامیلتونی ندارد. گراف پترسن کوچکترین گراف شبه هامیلتونی است یعنی اگرچه دور هامیلتونی ندارد، هر کدام از رأس هایش که حذف شوند می توان یک دور هامیلتونی در آن پیدا کرد. ( شکل۴ )