3NAE ≤p MAXCUT

נניח $\langle G,n+2m\rangle\in\mathrm{MAXCUT}$; אזי קיימת $U\subseteq V$ שהחתך המושרה על ידיה מכיל לפחות $n+2m$ קשתות.

צעד 1 — חסם עליון על האדומות. כאן דרוש טיעון הפוך מכל השאר: עד כה "לפחות", כעת "לכל היותר". תהי $C$ פסוקית והמשולש שלה. לא משנה מהי $U$: או ששלושת קודקודי המשולש באותו צד (אז $0$ חוצות), או שהם מתחלקים $2$–$1$ (אז בדיוק $2$). לכן לכל פסוקית לכל היותר $2$ קשתות אדומות בחתך, ובסך הכול לכל היותר $2m$.

צעד 2 — כפיית הכחולות. בחתך יש לפחות $n+2m$ קשתות ומהן לכל היותר $2m$ אדומות, ולכן לפחות $n$ כחולות. אבל בגרף יש בסך הכול בדיוק $n$ קשתות כחולות. לכן בחתך יש בדיוק $n$ כחולות — כולן. מכאן שלכל $i$ הקשת $x_i\overline{x_i}$ בחתך, כלומר בדיוק אחד מבין $x_i,\overline{x_i}$ ב-$U$.

צעד 3 — ההצבה. נגדיר $V(\ell)=1\iff\ell\in U$ לכל קודקוד ליטרל. מצעד 2 ההגדרה עקבית ומוגדרת היטב: מכל זוג $\{x_i,\overline{x_i}\}$ בדיוק אחד ב-$U$, ולכן בדיוק אחד מקבל $1$ והשני $0$.

צעד 4 — כל פסוקית מסופקת במובן NAE. בחתך בדיוק $n$ כחולות, ולכן מתוך לפחות $n+2m$ קשתות, לפחות $2m$ אדומות. מצד שני כל פסוקית תורמת לכל היותר $2$; אילו פסוקית אחת תרמה פחות מ-$2$, הסכום היה קטן מ-$2m$ — סתירה. לכן כל פסוקית תורמת בדיוק שתיים.

תהי $C$ פסוקית. אילו שלושת קודקודיה היו באותו צד היא הייתה תורמת $0$. לכן היא מתחלקת: קיים $\ell\in C$ עם $\ell\in U$, כלומר $V(\ell)=1$, וקיים $\ell'\in C$ עם $\ell'\notin U$, כלומר $V(\ell')=0$. זו בדיוק ההגדרה של סיפוק במובן NAE. מכיוון ש-$C$ שרירותית, $\varphi\in\mathrm{3NAE}$.