مقدمه


در نظریه گراف‌ یک سری از گراف‎ها وجود دارند که خاصند و به دلیل خصوصیاتشان و طرز ساخت یا کاربردی ترکیبیاتی و غیره از اهمیت خاصی برخوردارند مانند گراف پترسون که حتما درمورد  آن اطلاعاتی دارید.
گراف کنزر یکی از این گراف‎هاست، این گراف‌ها به نام مارتین کنزر نام‌گذاری شده‌اند که
برای اولین بار آنها را در سال ۱۹۵۵ بررسی کرد.


این گراف که با KG_n,k نشان داده می‎شود، گرافی است که رأس‌های آن نظیر زیرمجموعه‌های k-عضوی از یک مجموعه‎ی n-عضوی است.
بین دو رأس این گراف‌ یک یال وجود دارد اگر و تنها اگر زیرمجموعه‌های نظیر رأس‌ها ناسازگار باشند (اشتراکشان تهی باشد).
با توجه به روش ساخت یک گراف کنزر KG_n,k به‌سادگی می‎توان به خصوصیات زیر اشاره کرد:

1.  تعداد راس‎های گراف کنزر برابر است.

2. هر راس در گراف کنزر با راس دیگر مجاور است.

3.  گراف کامل n-رأسی، گراف کنزر KG_n,1 است و در شکل 1 هم مشاهده می‎شود.
 

شكل 1

4. در گراف کنزر اگر k=n/2 باشد، و n هم عددی زوج باشد، آن‎گاه  هر راس تنها با یک راس دیگر مجاور است و بنابراین گراف موردنظر شبیه نردبانی است که   پله دارد و در شکل 2 هم دو نمونه از این گراف‎ها نشان داده شده‌اند.

شكل 2

5. گراف  کنزر KG_5,2 با گراف پترسون ایزومورف است و در شکل 3 دیده می‎شود.

شكل 3