گراف کامل

گراف کامل گراف ساده‌ای است که در آن هر رأس به تمامی راس‌های دیگر به وسیلهٔ یک یال متصل است. معمولاً گراف کاملِ  راسی را با  نمایش میدهند. آغاز نظریه گراف‌ها معمولاً با کار اویلر بر روی  هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است.Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40. با این حال، تاریخچه گرافهای کامل به رسم‌های رامون یوی در قرن سیزدهم بازمی‌گردد، که رئوس گراف را در گوشه‌های چندضلعی منتظم قرار میداد... این رسم‌ها با عنوان گل رز عرفانی نیز شناخته می‌شوند..

 خواص 
 تعداد یالهای یک گراف کامل  راسی    است.
هر گراف کاملی گروهک بیشین خود است.
مکمل یک گراف کامل، گراف تهی است.
تعداد تطابق‌های کامل یک گراف کامل  راسی برابر است با . .

 مثال 
شکل پایین شامل گرافهای کامل که دارای یک تا هشت رأس هستند می‌باشد:
        100px 100px 100px 100px        120px 120px 120px 120px

 ماتریس مجاورت گراف کامل 
تمامی درایه‌های گراف کامل ۱ هستند به جز درایه‌های روی قطر اصلی که صفر هستند چون گراف کامل طوقه وجود ندارد.

 منابع 

 ریاضیات گسسته و کاربردهای آن 

رده:خانواده‌های پارامتری گراف‌ها
رده:گراف‌های منتظم
رده:نظریه گراف