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

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

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

נוסח המשפט

יהי $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}$ .