משפט מנטל

משפט מנטל בתורת הגרפים הוא משפט הקובע כי בהינתן גרף פשוט לא מכוון עם n צמתים וחסר משולשים (חסר מעגלים באורך 3), אז מספר הקשתות שלו הוא לכל היותר . החסם אותו נותן משפט מנטל הוא הדוק שכן הגרף הדו-צדדי המלא () הוא חסר משולשים וכן מספר הקשתות שלו הוא .

לפי השקילות הלוגית  נוכל לקבל ניסוח שקול למשפט הטוען כי אם בגרף G פשוט ולא מכוון יש יותר מ קשתות אז יש ב-G משולש.

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

הגדרה פורמלית 
יהי  גרף, נסמן , נניח כי לכל 3 צמתים  שונים בגרף, מתקיים , אז

הוכחה 
יהי  גרף חסר משולשים. נבנה ממנו גרף דו-צדדי  כך ש ,מה שיוכיח את המשפט, שכן גרף הוא דו צדדי אמ“ם אין בו מעגלים מאורך אי-זוגי, ובפרט באורך 3.

נסמן  הצומת בעל הדרגה המקסימלית. כמו כן, נסמן ב את  (קבוצת השכנים). כעת נביט בגרף הדו-צדדי המלא  על S ועל , נוכיח כעת כי , ומנוסחת לחיצות היידים, נוכל להסיק כי , וזה יסיים את ההוכחה.

יהי , נחלק למקרים:

אם , אז  שכן  היא הדרגה המקסימלית בגרף G, לפי הגדרת S .

אם , אז  מפני שגם בגרף G לא היו קשתות בין קודקודים S כיוון שG חסר משולשים (אם הייתה קשת בין  אז משולש בG). כמו כן  מפני שהמקרה גרוע ביותר הוא כאשר  (שטח ריבוע הוא מקסימלי)

הערות שוליים 

משפטים בתורת הגרפים