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

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

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