مکمل يک گراف

 گرافی را در نظر گرفته آن را  G می ناميم. حال گراف ديگری را در نظر بگيريد که مجموعه رئوس آن دقیقا مساوی با V(G) باشد و بين دو رأس آن يالی وجود داشته باشد اگر و فقط اگر در گراف G بين آن دو رأس يالی نباشد، چنين گرافی را مکمل گراف G می نامیم.  نوع ساده نوع پیچیده