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