کاهش به مسئله دو صدق‌پذیری

در این بخش به کاهش دو مسئله تشخیص دوبخشی بودن گراف و … به مسئله دوصدق‌پذیر می پردازیم.

برای حل این مسئله به کمک مسئله دوصدق‌پذیری ابتدا به ازای هر راس گراف مانند $v$ یک متغیر به‌نام $a_v$ در نظر می گیریم. حال به ازای هر دو راس مانند $v$ و $u$ که به هم یال دارند، دو بند $(a_v \lor \lnot a_u)\land (\lnot a_v \lor a_u)$ را اضافه کنیم. با گذاشتن $and$ بین تمامی بند‌ها عبارتی بولی بدست می آید با $n$ متغیر و $2*e$ بند($n$ برابر تعداد رئوس و $e$ برابر تعداد یال های گراف است). اگر بتوانیم به هر متغیر مقداری بدهیم که مقدار عبارت بولی صحیح باشد، آنگاه به ازای هر راس اگر مقدار متغیرش (در حالتی که کل عبارت صحیح است) صحیح بود رنگ سیاه، در غیر اینصورت رنگ سفید می دهیم. حال بدلیل صحیح بودن کل عبارت هیج دو راس مجاوری هم رنگ نیستند. همینطور اگر گراف دو بخشی بود، مقدار متغیر راس های یک بخش را صحیح و مقدار متغیر راس های بخش دیگر را نادرست درنظر بگیرید. مقدار عبارت بولی در این صورت صحیح می شود. پس با تشخیص دوصدق پذیری عبارت بدست آمده می توان دوبخشی بودن گراف داده شده را تشخیص داد.