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

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

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

נוסח המשפט

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

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

הוכחת המשפט

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

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

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

נכוון את צלעות המעגל $C$ לכיוון אחיד. תהי $a_{1},a_{2},\dotsc ,a_{k}$ סדרת $k$ השכנים השונים שיש ל$U$ על המעגל $C$, מסודרים לפי סדר הופעתם במעגל. לכל $1\leq i\leq k$ נסמן ב$u_{i}$ את השכן של $a_{i}$ ב$U$ וב$b_{i}$ את האיבר המופיע מיד אחרי $a_{i}$ במעגל $C$. נשים לב כי איברי $b_{i}$ שונים אחד מהשני, מכיוון שאיברי $a_{i}$ שונים אחד מהשני.

יהי $u\in U$ כלשהו. נטען כי הקבוצה $\left\{b_{1},b_{2},\dotsc ,b_{k}\right\}\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}$ באותו רכיב קשירות) ולבסוף ניקח את הצלע $ub_{i}$ כדי לחזור ל$b_{i}$.

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

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

• "A note on Hamiltonian circuits