תורת הגרפים - מעגל המילטון

nir9696

New member
תורת הגרפים - מעגל המילטון

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