משפט ארדש-צ'באטאל

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

את המשפט הוכיחו פאול ארדש וווצלאב צ'באטאל, במאמר שפרסמו יחדיו.

נוסח המשפט

יהי $G=(V,E)$ גרף פשוט עם לפחות 3 קודקודים. יהי $\alpha (G)$ מספר האי תלות של $G$ (גודל הקבוצה הבלתי תלויה הגדולה ביותר) ויהי $K\left(G\right)$ הקשירות הקודוקדית של G (המספר הקטן ביותר של קודקודים שיש להסיר מG על מנת להפוך אותו לגרף לא קשיר).

המשפט אומר שאם מתקיים $\alpha \left(G\right)\le K\left(G\right)$, אז $G$ מכיל מעגל המילטון.

הוכחת המשפט

נסמן $k=K\left(G\right)$, $n=\left|V\right|$. אז אם $k=1$ נקבל כי $\alpha \left(G\right)\le 1$ ולכן $\alpha \left(G\right)=1$. לכן בין כל שני קודקודים ב$G$ יש צלע ולכן $G$ קליקה. אבל אז $k=K\left(G\right)=n-1$, סתירה.

לכן נוכל להניח כי $k\ge 2$. יהי $C$ המעגל בעל האורך הגדול ביותר ב$G$. נטען כי $C$ מעגל המילטון. מאחר ש$k=K\left(G\right)\le \delta \left(G\right)$ (כאשר $\delta \left(G\right)$ הדרגה המזערית ב$G$), מתקיים כי $C$ מכיל לפחות $k+1$ קודקודים.

נסתכל בגרף $G(V\setminus V\left(C\right))$ (כלומר ב$G$ בלי הקודקודים של $C$ והצלעות שנוגעות בקודוקדים אלה). נניח בשלילה כי הוא אינו ריק. יהי $U$ רכיב קשירות בגרף זה. אז בגרף המקורי $G$, קבוצת קודקודי $U$ מחוברת ל$k$ שכנים שונים ב$C$ - אחרת נוכל לנתק את $U$ מהמעגל $C$ על ידי הסרת פחות מ$k$ קודקודים, בסתירה לכך שהקשירות הקודקודית של $G$ היא $k$.

נכוון את צלעות המעגל $C$ לכיוון אחיד. תהי $a_1,a_2,\dots ,a_k$ סדרת $k$ השכנים השונים שיש ל$U$ על המעגל $C$, מסודרים לפי סדר הופעתם במעגל. לכל $1\le i\le k$ נסמן ב$u_i$ את השכן של $a_i$ ב$U$ וב$b_i$ את האיבר המופיע מיד אחרי $a_i$ במעגל $C$. נשים לב כי איברי $b_i$ שונים אחד מהשני, מכיוון שאיברי $a_i$ שונים אחד מהשני.

יהי $u\in U$ כלשהו. נטען כי הקבוצה $\{b_1,b_2,\dots ,b_k\}\cup \left\{u\right\}$ היא קבוצה בלתי תלויה. זה יגרור סתירה, כי זו קבוצה בלתי תלויה בגודל $k+1$, כאשר הנחנו שהקבוצה הבלתי תלויה הגדולה ביותר היא בגודל לכל היותר $k$.

נראה ראשית שאין צלע בין $b_i$ ל$b_j$ כאשר $i<j$. לו הייתה כזו, יכולנו ליצור מעגל באורך גדול יותר ב$G$ בצורה הבאה: נתחיל ב$b_j$, נמשיך לאורך $C$ עד שנגיע ל$a_i$, משם נמשיך ל$u_i$ וממנו ל$u_j$ (זה אפשרי כי $u_i$ ו$u_j$ באותו רכיב קשירות) ומ$u_j$ נמשיך ל$a_j$ משם נלך על $C$ בכיוון הנגדי עד ל$b_i$ ומשם לבסוף ניקח את הצלע $b_i{b}_j$ כדי לחזור ל$b_j$.

בנוסף, נראה שאין צלע בין $b_i$ ל-$u$, לו הייתה כזאת יכולנו לקבל מעגל ארוך יותר באופן הבא: נתחיל ב$b_i$, נמשיך לאורך $C$ עד אשר נגיע ל$a_i$ נמשיך ל$u_i$ ומשם ל$u$ (זה אפשרי כי $u,u_i$ באותו רכיב קשירות) ולבסוף ניקח את הצלע $u{b}_i$ כדי לחזור ל$b_i$.

לכן קיבלנו כי הקבוצה $\{b_1,b_2,\dots ,b_k\}\cup \left\{u\right\}$ היא קבוצה בלתי תלויה באורך $k+1$, סתירה.

קישורים חיצוניים

• "A note on Hamiltonian circuits