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

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

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

 נוסח המשפט 
יהי  גרף פשוט עם לפחות 3 קודקודים. יהי  מספר האי תלות של  (גודל הקבוצה הבלתי תלויה הגדולה ביותר) ויהי  הקשירות הקודוקדית של G (המספר הקטן ביותר של קודקודים שיש להסיר מ־G על מנת להפוך אותו לגרף לא קשיר).

המשפט אומר שאם מתקיים , אז  מכיל מעגל המילטון.

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

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

נסתכל בגרף  (כלומר ב בלי הקודקודים של  והצלעות שנוגעות בקודוקדים אלה). נניח בשלילה כי הוא אינו ריק. יהי  רכיב קשירות בגרף זה. אז בגרף המקורי , קבוצת קודקודי  מחוברת ל שכנים שונים ב – אחרת נוכל לנתק את  מהמעגל  על ידי הסרת פחות מ קודקודים, בסתירה לכך שהקשירות הקודקודית של  היא .

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

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

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

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

לכן קיבלנו כי הקבוצה  היא קבוצה בלתי תלויה באורך , סתירה.

קישורים חיצוניים
 "A note on Hamiltonian circuits

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