گراف مکمل

در نظریه گراف، مکمّل یا معکوس گراف G، گراف H با رئوس یکسان است به طوری که دو رأس متمایز H مجاورند اگر و فقط اگر آن دو راس در G مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می شوند و تمام یال هایی که قبلاً وجود داشتند حذف می گردند. [ ۱]
فرض کنید G = ( V, E ) یک گراف ساده باشد و K مجموعهٔ تمام زیرمجموعه های ۲ - عضوی V است. در این صورت، H = ( V, K \ E ) گرافِ مکمّلِ گرافِ Gست، [ ۲] که در آن K \ E متمم نسبی E در K است. برای گراف های جهت دار، می توان مکمَل را به همین شکل تعریف کرد؛ یعنی به عنوان یک گراف جهت دار با مجموعه رئوس یک سان با استفاده از مجموعهٔ تمام زوج مرتب های ۲ - عضوی از V به عنوان K در عبارت مذکور.