یادآوری
گراف دو بخشی
گراف دو بخشی، گرافی است که بتوان مجموعه راس‌های آن را به دو مجموعه و چنان افراز کرد که هر یال آن دارای یک انتها در و یک انتها در باشد، به‌طوری‌که هیچ دو راس از یا هیچ دو راس از با هم مجاور نباشند، چنین افرازی را دوبخشی کردن گراف ساده می‌نامند.
کل رئوس
به‌عنوان نمونه:
اگر داشته باشیم:
گراف زیر دوبخشی است:
گرافی دوبخشی است، اگر و تنها اگر شامل هیچ دور با طول فرد نباشد.
گراف کامل دو بخشی
در دسته‌ای دیگر از گراف‌های ساده مجموعه راس زیر را:
می‌توان به دو زیر مجموعه زیر تجزیه کرد:
هر راس داخلی یکی از زیر مجموعه‌ها، دقیقا به‌وسیله یک یال به هرراس داخل زیر مجموعه دیگر متصل شده باشد، اما بر هر راس خود آن زیرمجموعه متصل نباشد، به‌چنین گراف‌هایی گراف کامل دوبخشی گویند.
یک گراف کامل دوبخشی با راس که به‌صورت نمایش داده می‌شود.
گراف زیر دوبخشی است:
تعریف گراف دوبخشی و احاطه‌گری
تعیین مجموعه احاطه و عدد احاطه‌گری در گراف‌های دوبخشی مانند سایر گراف‌ها می‌باشد، اما اگر گراف دوبخشی کامل باشد به‌سادگی مشخص می‌شود.
فرض کنیم گراف دوبخشی کامل باشد به‌طوری‌که .
اگر باشد،آن‌گاه :
اگر باشد، آن‌گاه :
برای انتخاب مجموعه احاطه‌گر فقط کافی است یک راس از مجموعه راس‌های اولی (راس‌های خانواده ) و یک راس از مجموعه راس‌های دومی (راس‌های خانواده ) را انتخاب کنیم.
این مجموعه احاطه‌گر، هم مینیموم و هم مینیمالِ دو عضوی است.
