בשיעור הראנו רדוקציה מ-IS ל-Max-Cut. הרדוקציה קיבלה קלט מהצורה (G,k) והחזירה את הפלט ( G, k) כפי שתואר בשיעור,…

בשיעור הראנו רדוקציה מ-$IS$ ל-$Max\text{-}Cut$. הרדוקציה קיבלה קלט מהצורה $(G,k)$ והחזירה את הפלט $(\widehat G,\widehat k)$ כפי שתואר בשיעור, כאשר הגרף $\widehat G$ הכיל גאדג'ט לכל קשת מן הגרף $G$.

הוכיחו את טענות העזר שעליהן הסתמכנו בהוכחת הרדוקציה:

1. כל גאדג'ט יכול לתרום לחתך כלשהו לכל היותר $4$ קשתות.
2. כל גאדג'ט המתאים לקשת ששני קצותיה ב-$U$ יכול לתרום לחתך כלשהו לכל היותר $3$ קשתות.