در این بخش به کاهش دو مسئله تشخیص دوبخشی بودن گراف و … به مسئله دوصدقپذیر می پردازیم.
برای حل این مسئله به کمک مسئله دوصدقپذیری ابتدا به ازای هر راس گراف مانند v یک متغیر بهنام av در نظر می گیریم. حال به ازای هر دو راس مانند v و u که به هم یال دارند، دو بند (av∨¬au)∧(¬av∨au) را اضافه کنیم. با گذاشتن and بین تمامی بندها عبارتی بولی بدست می آید با n متغیر و 2∗e بند(n برابر تعداد رئوس و e برابر تعداد یال های گراف است). اگر بتوانیم به هر متغیر مقداری بدهیم که مقدار عبارت بولی صحیح باشد، آنگاه به ازای هر راس اگر مقدار متغیرش (در حالتی که کل عبارت صحیح است) صحیح بود رنگ سیاه، در غیر اینصورت رنگ سفید می دهیم. حال بدلیل صحیح بودن کل عبارت هیج دو راس مجاوری هم رنگ نیستند. همینطور اگر گراف دو بخشی بود، مقدار متغیر راس های یک بخش را صحیح و مقدار متغیر راس های بخش دیگر را نادرست درنظر بگیرید. مقدار عبارت بولی در این صورت صحیح می شود. پس با تشخیص دوصدق پذیری عبارت بدست آمده می توان دوبخشی بودن گراف داده شده را تشخیص داد.