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

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

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

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

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

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

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

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

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

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

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

בנוסף, נראה שאין צלע בין <math>b_i</math> ל-<math>u</math>, לו הייתה כזאת יכולנו לקבל מעגל ארוך יותר באופן הבא: נתחיל ב<math>b_i</math>, נמשיך לאורך <math>C</math> עד אשר נגיע ל<math>a_i</math> נמשיך ל<math>u_i</math> ומשם ל<math>u</math> (זה אפשרי כי <math>u,u_i</math> באותו רכיב קשירות) ולבסוף ניקח את הצלע <math>ub_i</math> כדי לחזור ל<math>b_i</math>.

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

==קישורים חיצוניים==
*[https://web.archive.org/web/20170706082729/http://www.math-inst.hu/~p_erdos/1972-02.pdf "A note on Hamiltonian circuits] 

ארדש-צ'באטאל
קטגוריה:פאול ארדש