סריקה מצומת v הינה טיול בגרף המתחיל בצומת v. במהלך הטיול אין בוחרים קשת יותר מפעם אחת. בכל צעד נבחרת קשת באופן שרירותי מבין הקשתות הנוגעות בצומת הנוכחי, ועדיין לא נבחרו. הסריקה מסתיימת כאשר מגיעים לצומת שכל הקשתות הנוגעות בו נבחרו כבר. גרף קשיר ולא מכוון נקרא גרף תערוכה מצומת v אם כל סריקה מצומת v יוצרת מעגל אוילרי.
אני תקוע עם השאלה הזאת כבר תקופה. אני מנסה להפריד למיקרים אבל לא מצליח להבין לאיזה.
אשמח לעזרה 
נפריד לשלבים:
-
נניח כי G הינו גרף תערוכה מצומת v ונוכיח כי הוא גרף אוילרי מעגלי וכי v נמצא על כל מעגל פשוט של G. במקרה זה, כל סריקה מצומת v יוצרת מעגל אוילר. ניקח סריקה שרירותית והיא תיצור מעגל אוילר ולכן הגרף הוא אוילרי מעגלי. נניח בשלילה כי צומת v לא נמצא על מעגל פשוט, שנסמנו ב-C. נסתכל על גרף חדש G' אשר מתקבל מ-G ע"י הורדה של קשתות של C. דרגה של כל צומת בגרף G' תהיה זוגית. נבצע בו סריקה כלשהיא שמתחילה מצומת v. משיקולי זוגיות הדרגות, הסריקה תסתיים בצומת v. הסריקה הזאת הייתה יכולה להתקיים גם בגרף G, וגם בו היא הייתה נתקעת בצומת v כי לצומת זה בשני הגרפים נוגעות בדיוק אותן הקשתות. אבל בגרף G סריקה כזאת לא מכסה קשתות של מעגל C ולכן היא אינה מייצרת מעגל אוילרי. קיבלנו סתירה להיותו של גרף G תערוכה.
-
נניח כי G הוא גרף אוילרי מעגלי וכי v נמצא על כל מעגל פשוט של G ונוכיח כי G הינו גרף תערוכה מצומת v. במקרה זה, נסתכל על סריקה שרירותית המתחילה בצומת v. הגרף הוא אוילרי ולכן משיקולי זוגיות דרגות הצמתים, הסריקה תסתיים בצומת v גם כן. נניח בשלילה שהיא לא יצרה מעגל אוילר. זה אומר שהיא לא כיסתה את כל הקשתות של גרף G. נבחר קשת אחת כזאת, u-w. דרגה של w היא זוגית ולכן מספר קשתות שנוגעות ב-w ואשר לא השתמשנו בהן במהלך הסריקה הוא זוגי ולכן לפחות שתיים. אז לקשת u-w ניתן לצרף עוד קשת. נחזור על אותם השיקולים עבור הקצה השני של הקשת החדשה ובצורה כזאת נמשיך ונבנה מסלול של קשתות. גרף סופי ולכן המסלול הזה יחזור לצומת שכבר שייך למסלול הזה. אז סגרנו מעגל פשוט, ומעגל זה לא עובר דרך v. לכן, מעגל פשוט שנבנה לא מכיל את צומת v.
כך קיבלנו כי גרף G הינו גרף תערוכה מצומת v אם"ם הוא גרף אוילרי מעגלי ו-v נמצא על כל מעגל פשוט של G.