משפט מנטל

משפט מנטל בתורת הגרפים הוא משפט הקובע כי בהינתן גרף פשוט לא מכוון עם 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$ (שטח ריבוע הוא מקסימלי)