משפט טורן והולדת תורת הגרפים האקסטרמלית

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

הפעם אני רוצה לעסוק בתחום דומה בקומבינטוריקה (תת-תחום של תורת רמזי? המעמד הרשמי לא ממש חשוב) - תורת הגרפים האקסטרמלית. כפי שניתן לנחש, האובייקטים שלנו כאן הם גרפים (אבל נו באמת - איזה אובייקט ביקום לא ניתן לתיאור על ידי גרף?) ואנחנו רוצים להבין את תכונותיהם של הגרפים הקיצוניים ביותר שמקיימים (או שלא מקיימים) תכונה כלשהי. באופן קצת יותר קונקרטי, עבור תכונה \( \Phi \) כלשהי של גרפים, שאלה מרכזית היא זו: מה המספר המקסימלי של קשתות שגרף עם \( n \) צמתים יכול להכיל ועדיין לקיים את התכונה \( \Phi \)? המספר הזה מסומן לרוב כ-\( \mbox{ex}\left(n,\Phi\right) \) (אפשר לחשוב עליו כפונקציה של \( n \) עם פרמטר \( \Phi \)). לא תמיד אפשר לדעת במדויק את \( \mbox{ex}\left(n,\Phi\right) \), כמובן, ולרוב מסתפקים בהערכה.

המקרה המעניין הראשון הוא זה שבו \( \Phi \) היא התכונה “להכיל תת-גרף מסויים”. אז אנחנו שואלים את השאלה הקלאסית של תורת רמזי - מתי אובייקט הוא גדול דיו כדי שמבנה מסויים יצוץ בתוכו לבטח? ומשפט טורן מטפל בתת גרף פשוט במיוחד: קליק. קליק מגודל \( t \), שאותו אסמן ב-\( K_{t} \), הוא פשוט קבוצה של \( t \) צמתים שכולם מחוברים אלה לאלה בקשתות. שימו לב להבדל בין זה ומשפט רמזי, שמדבר על מספר הצמתים שצריך להיות בגרף לפני שיצוץ בו קליק מגודל מסויים או קבוצה בלתי תלויה מגודל מסויים; כאן מספר הצמתים \( n \) קבוע ונתון מראש ואנחנו רוצים לדעת מה מספר הקשתות; ולהבדיל ממשפט רמזי, כאן אנחנו יודעים את \( \mbox{ex}\left(n,K_{t}\right) \) במדויק וגם יודעים בדיוק איך הגרפים הקיצוניים (בעלי המספר המקסימלי של קשתות שאינם מכילים את \( K_{t} \)) נראים.

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

התעלול הוא להשתמש במה שנקרא “גרף דו צדדי”. גרף דו צדדי הוא כזה שניתן לחלק את צמתיו לשתי קבוצות - הטובים והרעים - כך שכל צומת שייך לאחת מהקבוצות, וכל קשת בהכרח מחברת בין טוב ורע; אין קשת בין שני טובים, או קשת בין שני רעים. בגרף כזה לא יכול להיות משולש, כי בקבוצה של שלושה קודקודים יש שני טובים (שאינם מחוברים בקשת) או שני רעים (שאינם מחוברים בקשת). מצד שני, בגלל שאנחנו יודעים שבגרף דו צדדי מובטח לנו שלא יהיה משולש אנחנו יכולים להתפרע ולהוסיף כמה קשתות שבא לנו כל עוד הן לא מחברות שני טובים או שני רעים. באופן כללי אם יש \( a \) טובים ו-\( b \) רעים וכל טוב מחובר לרע בקשת יהיו לנו \( ab \) קשתות בגרף. מכיוון ש-\( n=a+b \), זה אומר שיהיו לנו \( a\left(n-a\right)=na-a^{2} \) קשתות בגרף, והשאלה היא איזה ערך של \( a \) ייתן לנו את המקסימום. קצת חשבון דיפרנציאלי (אני לא אומר שאין דרכים אחרות, ועוד נראה כאלו) נותן בקלות את התשובה הלא מפתיעה - \( a=\frac{n}{2} \) (אם \( n \) אי זוגי מעגלים כלפי מטה או מעלה, זה לא משנה). כלומר המספר המקסימלי של קשתות מתקבל כאשר מחלקים את הגרף לשתי קבוצות שוות של צמתים, ואז יהיו \( \frac{n^{2}}{4} \) קשתות. כלומר, \( \mbox{ex}\left(n,K_{3}\right)=\frac{n^{2}}{4} \). כל זה היה ידוע בימיו של טורן; המשפט שלו הוא פשוט הכללה רדיקלית שנותנת את \( \mbox{ex}\left(n,K_{t}\right) \)לכל \( t \).

כדי לפשט טיפה את הסימונים מכאן ואילך אניח שאנחנו מנסים למצוא את \( \mbox{ex}\left(n,K_{t+1}\right) \); עוד שניה יהיה ברור לכולם למה עדיף לדבר על \( t+1 \) כאן.

הצעד הראשון הוא לנסות ולבנות גרפים גדולים ככל האפשר שאינם מכילים קליק מגודל \( t+1 \). ממש מתבקש להכליל כאן את הרעיון שכבר הצגתי - במקום גרף דו-צדדי, לקחת גרף \( t \) צדדי, כלומר כזה שבו הצמתים מחולקים ל-\( t \) קבוצות ואין קשת בין שני חברי אותה קבוצה (אבל כל צומת מקבוצה מסויימת יכול להיות מחובר לכל צומת מכל קבוצה אחרת). ההוכחה שאין בגרף כזה קליק מגודל \( t+1 \) זהה: אם יש \( t+1 \) צמתים יש לפחות שני צמתים מאותה קבוצה (זהו עקרון שובך היונים בפעולה) ולכן זוג צמתים בלי קשת ביניהם).

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

לצורך פשטות נניח מכאן ואילך ש-\( t \) מחלק את \( n \), אחרת סתם הסימונים שלנו יהיו מסורבלים בהרבה. במקרה הזה, כל הקבוצות יהיו מאותו גודל - \( \frac{n}{t} \). כמה קשתות יהיו? כמו שראינו קודם, בין כל שתי קבוצות של צמתים מחברות \( \frac{n^{2}}{t^{2}} \) קשתות; ויש לנו \( {t \choose 2}=\frac{t\left(t-1\right)}{2} \) זוגות (למי שלא מכיר את הסימון הזה - נעים להכיר). לכן יש בסך הכל \( \frac{t\left(t-1\right)}{2}\cdot\frac{n^{2}}{t^{2}}=\frac{t-1}{t}\frac{n^{2}}{2}=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \) קשתות.

כעת אפשר לנסח את משפט טורן. פורמלית, הוא אומר ש-\( \mbox{ex}\left(n,K_{t+1}\right)=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \), אבל ניסוחים כאלו הם אחד מהדברים השנואים עלי במתמטיקה. לא כי הוא לא נכון או לא מדויק או כל דבר אחר, אלא כי אם זה מה שתראו למישהו מבחוץ הוא לא יבין את הקטע. אוקיי, אז יש לנו איזו נוסחה לא יפה במיוחד עבור \( \mbox{ex}\left(n,K_{t+1}\right) \), אז מה? הפואנטה כאן לטעמי היא שמשפט טורן אומר שהגרפים האקסטרמליים במקרה הזה הם אכן הגרפים ה-\( t \) צדדיים שבנינו - דרך הרבה יותר ציורית ויפה להבין את המספר \( \left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \) (כמובן, לערך המספרי יש חשיבות ביישומים של המשפט). כך זה תמיד במתמטיקה - המטרה היא לא איזו נוסחה סגורה מפוצצת, אלא ההבנה של התופעה שמאחורי הנוסחה (הבנה שלא תהיה שלמה עד שההוכחות לא יסייעו לנו להבין למה הגרפים ה-\( t \) צדדיים הם אכן אקסטרמליים).

אני רוצה להציג שלוש הוכחות למשפט. הראשונה של טורן עצמו שהיא פשוטה ויפה וברורה. השניה של אלון וספנסר שהיא קסם וודו מוחלט, אבל ממחישה יפה את כוחה של השיטה ההסתברותית (שאלון וספנסר כתבו את הספר עליה, תרתי משמע). והשלישית היא אלמנטרית לחלוטין, מבהירה מיידית ובצורה מוחלטת למה הגרפים ה-\( t \) צדדיים הם האקסטרימליים, ולא ברור מי המציא אותה. כל ההוכחות מגיעות מהספר Proofs from THE BOOK שכולל גם שתי הוכחות שלא אראה כאן.

ראשית, ניסוח מדויק של המשפט שכוחו יפה גם ל-\( n \) שלא מתחלק על ידי \( t \): אם \( G \) הוא גרף בעל \( n \) צמתים ואין בו קליק מגודל \( t+1 \) (כאשר \( t\ge2 \)), אז מספר הקשתות ב-\( G \) הוא לא יותר מ-\( \left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \).

נתחיל עם טורן. טורן מוכיח את המשפט באינדוקציה על \( n \), כש-\( t \) קבוע. כל עוד \( n\le t \) אז לא משנה אילו קשתות יהיו בגרף, לא יוכל להיות בו קליק מגודל \( t+1 \) כי אין מספיק צמתים; לכן צריך לוודא שמספר הקשתות הכולל בגרף לא יכול לעלות על החסם. מספר הקשתות המקסימלי האפשרי בגרף עם \( n \) צמתים הוא \( \frac{n\left(n-1\right)}{2} \), ובעזרת אי השוויון \( n\le t \) מקבלים:

\( \frac{n\left(n-1\right)}{2}\le\left(t-1\right)\frac{n}{2}\le\frac{t-1}{t}\cdot\frac{n^{2}}{2}=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \)

כך שעם זה סיימנו. החלק המעניין הוא לטפל במקרה שבו \( n>t \). מספיק להראות שבגרף עם מספר קשתות מקסימלי (ביחס לתכונה “לא מכיל את \( K_{t+1} \)) מתקיים החסם הנדרש, כי לכל גרף אחר אפשר להוסיף קשתות עד שמגיעים לגרף מקסימלי שכזה. גרף מקסימלי שכזה בהכרח יכיל את \( K_{t} \) (כי אם לא, הוא לא היה מקסימלי; הוספה של קשת לא הייתה יכול ליצור את \( K_{t+1} \) כי מ-\( K_{t+1} \) אפשר לקבל את \( K_{t} \) על ידי הסרה של קשת אחת וסילוק אחד הצמתים שמחוברים אליה). הרעיון הוא כעת לחלק את הגרף לשני חלקים: \( A \) תהיה קבוצת הצמתים של הקליק מגודל \( t \) הזה, ו-\( B \) תהיה קבוצת שאר הצמתים.

ב-\( A \) יש בדיוק \( {t \choose 2} \) קשתות שהרי בין כל זוג צמתים שם יש קשת. על \( B \) אנחנו יכולים להשתמש בהנחת האינדוקציה כי מספר הצמתים בה קטן מ-\( n \), כך שאנחנו יודעים שיש בה לכל היותר \( \left(1-\frac{1}{t}\right)\frac{\left(n-t\right)^{2}}{2} \) קשתות. אילו עוד קשתות יכולות להתקיים בגרף? כאלו שמחברות את \( A \) עם \( B \). כל צומת ב-\( B \) יכולה להתחבר כמעט לכל הצמתים של \( A \), אבל רק כמעט; אם היא תתחבר לכל הצמתים של \( A \), אז היא יחד עם \( A \) יהוו קליק מגודל \( t+1 \). לכן כל צומת מ-\( B \) מחוברת בקשת לכל היותר ל-\( t-1 \) צמתים מ-\( A \). אלו כל האבחנות שצריך, והיתר הוא חשבון מכולת. אנחנו מקבלים שמספר הקשתות הכולל בגרף חסום על ידי:

\( {t \choose 2}+\left(1-\frac{1}{t}\right)\frac{\left(n-t\right)^{2}}{2}+\left(n-t\right)\left(t-1\right) \)

אחרי סידור מחדש קטן מקבלים שזה שווה ל:

\( \left(t-1\right)\left[\frac{t}{2}+\frac{\left(n-t\right)^{2}}{2t}+\left(n-t\right)\right]=\left(t-1\right)\left[\frac{t}{2}+\frac{\left(n-t\right)\left(n+t\right)}{2t}\right] \)

\( =\left(t-1\right)\left[\frac{t^{2}+n^{2}-t^{2}}{2t}\right]=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \)

כמו קסם, קיבלנו לבסוף בדיוק את החסם שרצינו.

כמובן, אין כאן שום קסם אמיתי, זה היופי בהוכחה הזו - התוצאה חייבת להתקבל, אין מנוס מכך. יש לנו כאן דוגמה קלאסית להוכחה באינדוקציה: ראשית, טורן מזהה מרכיב כלשהו שחייב להופיע בגרף אקסטרימלי כלשהו (\( K_{t} \)). האבחנה הזו היא המפתח לנצחון, ומאותו רגע ההמשך מתבקש: לפרק את הגרף, למתוח כמה קשתות שרק אפשר בין הרכיבים, ולהשתמש בהנחת האינדוקציה על מה שנשאר. בעצם טורן מראה כאן ש-\( \mbox{ex}\left(n,K_{t+1}\right) \) מקיים את נוסחת הנסיגה \( \mbox{ex}\left(n,K_{t+1}\right)=\mbox{ex}\left(n-t,K_{t+1}\right)+{t \choose 2}+\left(n-t\right)\left(t-1\right) \) עבור \( n>t \), רק שכאן אין לנו צורך לפתור את הנוסחה הזו כי כבר היה לנו ניחוש מוצלח לגבי הערך של \( \mbox{ex}\left(n,K_{t+1}\right) \) מלכתחילה (בסיטואציות קומבינטוריות אחרות לא יהיה לנו כזה ואז נוסחת נסיגה שכזו תעזור גם להבין מה בדיוק הערך שאנחנו מחפשים).

נעבור כעת להוכחה השניה, של אלון וספנסר. הם לוקחים גרף כלשהו \( G \) בעל \( n \) צמתים שמסומנים לצורך נוחות ב-\( v_{1},\dots,v_{n} \), מסמנים ב-\( d_{i} \) את הדרגה של הצומת \( v_{i} \), כלומר מספר הקשתות שמחוברות אליו. כעת, אם נסמן ב-\( \omega\left(G\right) \) את גודל הקליק הגדול ביותר ב-\( G \), אלון וספנסר טוענים שמתקיים:

\( \omega\left(G\right)\ge\sum_{i=1}^{n}\frac{1}{n-d_{i}} \)

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

אז איך הטענה מסיימת את ההוכחה? כאן שולפים כלי מתמטי סטנדרטי מהשרוול - אי שוויון קושי-שוורץ. לאי השוויון הזה מספר ניסוחים ואבחר את הניסוח הפשוט יחסית שרלוונטי עבורנו: אם \( a_{1},\dots,a_{n} \) ו-\( b_{1},\dots,b_{n} \) הן סדרות מספרים אז:

\( \left(\sum_{i=1}^{n}a_{i}b_{i}\right)^{2}\le\left(\sum_{i=1}^{n}a_{i}^{2}\right)\left(\sum_{i=1}^{n}b_{i}^{2}\right) \)

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

השימוש כאן בקושי-שוורץ הוא פשוט יחסית. נבחר \( a_{i}=\sqrt{n-d_{i}} \) ו-\( b_{i}=\left(\sqrt{n-d_{i}}\right)^{-1} \), נציב בנוסחה ונקבל:

\( n^{2}\le\left(\sum_{i=1}^{n}\left(n-d_{i}\right)\right)\left(\sum_{i=1}^{n}\frac{1}{n-d_{i}}\right)\le\omega\left(G\right)\sum_{i=1}^{n}\left(n-d_{i}\right) \)

עכשיו יש לנו עוד שני תעלולים לשלוף מהשרוול: ראשית, אנחנו מניחים ש-\( \omega\left(G\right)\le t \) - זו ההנחה הבסיסית שלנו, לפיה הגרף לא מכיל את הקליק \( K_{t+1} \). שנית, יש לנו דרך לקשר בין הדרגות של כל הצמתים בגרף ובין מספר הקשתות בו. אם מספר הקשתות הוא \( e \), אז בכל גרף (סופי) שהוא מתקיים השוויון \( 2e=\sum_{i=1}^{n}d_{i} \), שכן כל קשת בגרף תורמת 1 לדרגות של שני הצמתים שהיא מחוברת אליהם. מכל אלה אפשר להסיק כעת:

\( n^{2}\le t\cdot\left(n^{2}-2e\right) \)

וכל שנשאר הוא ללהטט קצת כדי לחלץ את \( e \). פתיחת סוגריים, העברת אגפים, ונקבל:

\( 2et\le n^{2}\left(t-1\right) \)

חלוקה ונקבל:

\( e\le\left(1-\frac{1}{t}\right)\frac{n^{2}}{2} \)

בדיוק מה שרצינו.

בינתיים זה היה טכני ולא הכי מעניין, אני חייב להודות; לב ההוכחה הוא בטענה \( \omega\left(G\right)\ge\sum_{i=1}^{n}\frac{1}{n-d_{i}} \) וההוכחה ההסתברותית שלה שאציג כעת.

במבט ראשון לא ברור איך הסתברות יכולה להשתחל לכאן. הגרף \( G \) נתון וקבוע; מה בדיוק נגריל ואיך? הרעיון של אלון וספנסר הוא להגריל סדר על הצמתים - פורמלית, פרמוטציה \( \pi \) כלשהי שלהם, כשכל פרמוטציה נבחרת בהסתברות שווה, \( \frac{1}{n!} \). נניח שהצמתים \( v_{1},\dots,v_{n} \) כבר מסודרים על פי הפרמוטציה הזו, ונגדיר קבוצת צמתים \( C_{\pi} \) שמכילה את כל הצמתים \( v_{i} \) שמחוברים בקשת לכל הצמתים שבאים לפניהם בפרמוטציה, כלומר לכל \( v_{j} \) כך ש-\( j<i \).

הנקודה המהותית כאן היא ש-\( C_{\pi} \) היא קליק. למה? ובכן, קחו ב-\( C_{\pi} \) את הצומת עם האינדקס המקסימלי; על פי הגדרה, הוא מחובר לכל הצמתים עם אינדקס קטן יותר ובפרט לכל צמתי \( C_{\pi} \). כעת קחו את הצומת המקסימלי הבא בתור… הבנתם את הרעיון.

יפה, אז הצלחנו להגדיר איכשהו מרחב הסתברות שמערב קליקים. אנחנו מעוניינים בחסם כלשהו על גדלי הקליקים, אז נגדיר משתנה מקרי \( X=\left|C_{\pi}\right| \) - גודל \( C_{\pi} \). בגלל האופן שבה \( C_{\pi} \) נבנתה, קל לפרק את \( X \) לסכום של אינדיקטורים (משתנים מקריים שמקבלים 0 או 1 בלבד): \( X=\sum_{i=1}^{n}X_{i} \) כאשר \( X_{i} \) מקבל 1 אם \( v_{i} \) מחובר בקשת לכל הצמתים שקדמו לו.

כעת השאלה הפשוטה היא - מה ההסתברות ש-\( X_{i}=1 \)? מכיוון שכל הקשתות כבר נקבעו, זה תלוי בדרגה של \( v_{i} \): אם \( v_{i} \) מחובר ל-\( d_{i} \) צמתים, ההסתברות לכך שכל הצמתים שיהיו לפני \( v_{i} \) בפרמוטציה יהיו מתוך \( d_{i} \) הצמתים שהוא מחובר אליהם היא בעצם ההסתברות שמבין כל \( n-d_{i} \) הצמתים שאינם מחוברים אל \( v_{i} \), כולל \( v_{i} \) עצמו, יהיה זה \( v_{i} \) שמופיע ראשון. מכיוון שיש סימטריה בין כל \( n-d_{i} \) הצמתים הללו, ההסתברות לכך היא \( \frac{1}{n-d_{i}} \) (אתם מוזמנים לעשות חישוב פורמלי אם לא שוכנעתם).

זה מסיים את העניין אם זוכרים מה קורה בדרך כלל בשלב הזה בשיטה ההסתברותית. תוחלת של אינדיקטור היא ההסתברות שהוא יקבל 1, כלומר \( \mbox{E}\left[X_{i}\right]=\frac{1}{n-d_{i}} \). לינאריות התוחלת נותנת לנו כעת

\( \mbox{E}\left[X\right]=\mbox{E}\left[\sum_{i=1}^{n}X_{i}\right]=\sum_{i=1}^{n}\mbox{E}\left[X_{i}\right]=\sum_{i=1}^{n}\frac{1}{n-d_{i}} \)

ואנחנו מסיימים כי במרחב ההסתברות שלנו חייב להיות איבר שנותן ל-\( X \) לפחות את ערך התוחלת שלו, כלומר קליק שגודלו לפחות \( \sum_{i=1}^{n}\frac{1}{n-d_{i}} \).

שלא יהיה לכם ספק; אני לא מקבל שום אינטואיציה ל”מה הולך פה” מההוכחה הזו. היא פשוט מגניבה.

נעבור כעת להוכחה השלישית, שכנראה מבהירה הכי טוב “מה הולך פה”. מה שההוכחה מראה הוא שהגרף האקסטרמלי חייב להיות גרף \( k \)-צדדי כלשהו. כבר הגענו קודם למסקנה שמבין הגרפים ה-\( k \) צדדיים, הכי טוב הוא גרף \( t \) צדדי שבו כל הצדדים כמעט מאותו גודל (הפרש 1 לכל היותר בין כל שני צדדים), כי אם זה לא כך ניתן להזיז צמתים ולהגדיל את מספר הקשתות (וגרף \( t+1 \) צדדי כבר יכיל קליק מגודל \( t+1 \)).

גרף \( k \)-צדדי כלשהו מאופיין בדרך כלל על ידי ההגדרה ה”גלובלית” שלפיה “יש חלוקה של צמתי הגרף ל-\( k \) קבוצות, כך ש…”. אך למעשה, קיימת גם הגדרה “לוקלית” פשוטה במקרה שבו הגרף מכיל את כל הקשתות האפשריות: גרף הוא \( k \)-צדדי מלא, עבור \( k \) כלשהו, אם לכל זוג צמתים \( u,v \) שמחובר בקשת, וצומת נוסף \( w \), \( w \) חייב להיות מחובר ל-\( u \) או ל-\( v \).

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

למה אם הטענה נכונה הגרף הוא \( k \) צדדי מלא? ובכן, למי שמכיר את המושג: כי היחס “\( u,v \) לא מחוברים בקשת” הוא יחס שקילות; ולמי שלא מכיר, אפשר לבנות את הצדדים כך - ניקח צומת תמים \( u \), ונגדיר את “הצד של \( u \)” בתור אוסף כל הצמתים ש-\( u \) לא מחובר אליהם. לא ייתכן שבקבוצה הזו יהיו שני צמתים \( v,w \) שמחוברים בקשת (כי אז העובדה ש-\( u \) לא מחובר לאף אחד מהם סותרת את הטענה שלנו), לכן זה אכן צד חוקי של גרף \( k \) צדדי. בנוסף, אם ניקח צומת \( v \) כלשהו בצד הזה, הוא יהיה חייב להיות מחובר לכל צומת שאינה באותו צד איתו; כי אם יש צומת \( w \) שאינה באותו צד איתו אז על פי הגדרת הצד, \( w \) מחובר ל-\( u \), ולא ייתכן ש-\( v \) לא יהיה מחובר לא ל-\( u \) ולא ל-\( w \).

יפה, אז יש לנו אפיון לוקלי פשוט, וכל שצריך להראות הוא שהאפיון מתקיים בגרף האקסטרמלי. נניח בשלילה שהוא לא, אז יש לנו שלושה צמתים בגרף: \( u,v,w \), כך ש-\( u,v \) מחוברים בקשת ואילו \( w \) לא מחובר לאף אחד מהם. הרעיון הוא לבנות עכשיו מהגרף הקיים גרף חדש שבו יש יותר קשתות ואותו מספר צמתים ועדיין אין בו את \( K_{t+1} \), בסתירה לאקסטרימליות של הגרף שלנו.

איך עושים את זה? פשוט: מעיפים מהגרף את אחד מהצמתים \( u,v,w \) שיש לו מעט קשתות ושמים במקומו עותק של אחד מהצמתים האחרים. אם למשל מתקיים ש-\( d\left(u\right)>d\left(w\right) \), אז נעיף מהגרף את \( w \); בכך איבדנו \( d\left(w\right) \) קשתות. כפיצוי, נוסף לגרף צומת \( u^{\prime} \) שמחובר בדיוק לאותם צמתים ש-\( u \) מחובר אליהם; זה ייתן לנו עוד \( d\left(u\right) \) קשתות, כלומר הרווחנו. לא קשה לראות שהוספת \( u^{\prime} \) לגרף לא יכולה ליצור קליק מגודל \( t+1 \): אם יש קליק כזה, אז היה קליק כזה גם בגרף המקורי, רק עם \( u \) במקום \( u^{\prime} \) (לא ייתכן שיש קליק שמערב הן את \( u \) והן את \( u^{\prime} \) יחד, שכן אין קשת ביניהם).

באופן דומה מטפלים במקרה שבו \( d\left(v\right)>d\left(w\right) \). המקרה היחיד שנותר לנו הוא זה שבו \( d\left(w\right)\ge d\left(u\right),d\left(v\right) \). כאן נעיף מהגרף את \( u,v \) שניהם גם יחד ונשים שני עותקים של \( w \); הסיבה שבגללה נרוויח כך קשת היא שכשמסירים את \( u,v \) לא מאבדים \( d\left(u\right)+d\left(v\right) \) קשתות אלא רק \( d\left(u\right)+d\left(v\right)-1 \) קשתות, שכן הקשת המשותפת של \( u,v \) מוסרת רק פעם אחת. זה מסיים את ההוכחה הזו.

למשפט יש עוד מספר הוכחות, יפות לא פחות, אבל אני חושב שכבר הבאתי מספיק להפעם; אני מקווה שעכשיו ברור לכל הקוראים “מה הולך שם” וגם למה זה מעניין.