گراف خودمکمل

گراف خود مکمل گرافی است که با مکمل خود یک ریخت است. دوتا از ساده ترین گراف های خود مکمل یک گراف مسیری با ۴ راس و گراف دوری با ۵ راس است.
هر گراف ایده آلی یک گراف خود مکمل است. به طور مثال گراف ایده آل با ۹ راس نام لاتین ۳×3 rook's graph یک گراف خودمکمل است زیرا دارای یک تقارن است که راسی را در مرکز گراف ثابت نگه می دارد و مکان ۴ راس کناری نزدیک مرکز را با ۴ راس گوشه ای شبکه عوض می کند. همهٔ گراف های خودمکمل که به شدت منظم هستند با تعداد راس کمتر از ۳۷ یک گراف ایده آل هستند؛ گراف های ب شدت منظم با تعداد گره ۳۷ و ۴۱ و ۴۹ نیز وجود دارد که نیستند.گراف رادو هم یک گراف خودمکمل نامتناهی است.
هرگراف خود مکمل همبند است.یک گراف خودمکل با n راس دقیقاً به اندازهٔ نصف تعداد یال های گراف کامل یال دارد به عبارت دیگر 4/(n(n-۱ و به شرط اینکه تعداد گره بیشتر از ۱ باشد حتماً دارای یک قطر به اندازه ۲ یا ۳ است. چون (n(n-1 باید بر ۴ بخش پذیر باشد پس n به پیمانه ۴ باید با ۰ یا ۱ هم ارز باشد؛ ب طور مثال یک گراف کامل ۶راسه نمی تواند یک گراف خود مکمل باشد.
مشکل تشخیص همریخت بودن دو گراف و تشخیص خودمکمل بودن یک گراف همان مسئله عمومی همریختی گراف است.