שאלת מבחן במתמטיקה בדידה - גרפים

יהי $G = (V, E)$ גרף פשוט קשיר. (א) הוכיחו: אם כל קודקוד ב-$G$ הוא מדרגה זוגית, אז $G$ מכיל מעגל אוילרי. (ב) יהי $G$ גרף קשיר עם $|V| = 6$ שבו בדיוק 2 קודקודים מדרגה 3 ושאר הקודקודים מדרגה 2. האם קיים ב-$G$ מסלול אוילרי (פתוח)? נמקו.

רמז: עבור (א): זהו משפט אוילר הקלאסי — אפשר לצטט אותו. עבור (ב): מסלול אוילרי פתוח (לא מעגל) קיים אמ"מ הגרף קשיר ויש בו **בדיוק שני** קודקודים מדרגה אי-זוגית. מה דרגת הקודקודים שלנו?

פתרון: **(א)** זהו **משפט אוילר**: גרף קשיר מכיל מעגל אוילרי (מסלול סגור העובר בכל צלע בדיוק פעם אחת) אם ורק אם כל קודקודיו בעלי דרגה זוגית. **הוכחת הכיוון הנדרש ($\Leftarrow$):** נבנה מעגל אוילרי באלגוריתם: נתחיל מקודקוד כלשהו $v$ ונלך לאורך צלעות (בלי לחזור על צלע). מאחר שכל דרגה זוגית, בכל פעם שנכנסים לקודקוד אפשר גם לצאת ממנו — עד שחוזרים ל-$v$, ומקבלים מעגל $C$. אם $C$ לא מכסה את כל הצלעות, מקשירות $G$ קיים קודקוד $u$ על $C$ עם צלעות שלא ב-$C$. נבנה מעגל נוסף מ-$u$ (הגרף ללא צלעות $C$ עדיין בעל דרגות זוגיות) ונאחד. נמשיך עד שכל הצלעות מכוסות. $\blacksquare$ **(ב)** ב-$G$ יש בדיוק 2 קודקודים מדרגה 3 (אי-זוגית) ו-4 קודקודים מדרגה 2 (זוגית). לפי משפט אוילר: גרף קשיר מכיל **מסלול אוילרי פתוח** אמ"מ יש בו בדיוק **שני** קודקודים מדרגה אי-זוגית (והמסלול מתחיל באחד ומסתיים בשני). ב-$G$ יש בדיוק 2 קודקודים מדרגה אי-זוגית, ו-$G$ קשיר. לכן **כן, קיים ב-$G$ מסלול אוילרי פתוח** המתחיל באחד משני הקודקודים מדרגה 3 ומסתיים בשני. $\blacksquare$