משפט מנטל

משפט מנטל בתורת הגרפים הוא משפט הקובע כי בהינתן גרף פשוט לא מכוון עם n צמתים וחסר משולשים (חסר מעגלים באורך 3), אז מספר הקשתות שלו הוא לכל היותר $\left\lfloor {\frac {n^{2}}{4}}\right\rfloor$ . החסם אותו נותן משפט מנטל הדוק שכן הגרף הדו-צדדי המלא ( $K_{\lfloor {\frac {n}{2}}\rfloor ,\lceil {\frac {n}{2}}\rceil }$ ) הוא חסר משולשים וכן מספר הקשתות שלו הוא $\left\lfloor {\frac {n^{2}}{4}}\right\rfloor$ .

לפי הזהות $\alpha \implies \beta \equiv \urcorner \beta \implies \urcorner \alpha$ נוכל לקבל ניסוח שקול למשפט הטוען כי אם בגרף G פשוט ולא מכוון יש יותר מ $\left\lfloor {\frac {n^{2}}{4}}\right\rfloor$ קשתות אז יש ב-G משולש.

משפט מנטל הוא מקרה פרטי של משפט טורן.

הגדרה פורמלית

יהי $G=<V,E>$ גרף, נסמן $|V|=n$ , נניח כי לכל 3 צמתים $v_{1},v_{2},v_{3}\in V$ שונים בגרף, מתקיים $\urcorner (\{v_{1},v_{2}\}\in E\wedge \{v_{2},v_{3}\}\in E\wedge \{v_{1},v_{3}\}\in E)$ , אז $|E|\leq \lfloor {\frac {n^{2}}{4}}\rfloor$

הוכחה

יהי $G=<V,E>$ גרף חסר משולשים. נבנה ממנו גרף דו-צדדי $G'=<V,E'>$ כך ש $|E|\leq |E'|\leq \lfloor {\frac {n^{2}}{4}}\rfloor$ ,מה שיוכיח את המשפט, שכן גרף הוא דו צדדי אמ“ם אין בו מעגלים מאורך אי-זוגי, ובפרט באורך 3.

נסמן $v\in V$ הצומת בעל הדרגה המקסימלית. כמו כן, נסמן ב $S$ את $\{u\in V|\{v,u\}\in E\}$ (קבוצת השכנים). כעת נביט בגרף הדו-צדדי המלא $G'=<V,E'>$ על S ועל $V\setminus S$ , נוכיח כעת כי $\forall w\in V.deg_{G}(w)\leq deg_{G'}(w)$ , ומנוסחת לחיצות היידים, נוכל להסיק כי $|E|\leq |E'|$ , וזה יסיים את ההוכחה.

יהי $w\in V$ , נחלק למקרים:

אם $w\notin S$ , אז $deg_{G'}(w)=|S|\geq deg_{G}(w)$ שכן $|S|$ היא הדרגה המקסימלית בגרף G, לפי הגדרת S .

אם $w\in S$ , אז $deg_{G'}(w)=|V\setminus S|\geq deg_{G}(w)$ מפני שגם בגרף G לא היו קשתות בין קודקודים S כיוון שG חסר משולשים (אם הייתה קשת בין $u_{1},u_{2}\in S$ אז $v-u_{1}-u_{2}-v$ משולש בG). כמו כן $|E'|\leq \lfloor {\frac {n^{2}}{4}}\rfloor$ מפני שהמקרה גרוע ביותר הוא כאשר $|S|=\lfloor {\frac {n}{2}}\rfloor \wedge |V\setminus S|=\lceil {\frac {n}{2}}\rceil$ (שטח ריבוע הוא מקסימלי)^[1]