מעגל אוילר ונוסחת אוילר

מעגל אוילר

תרגיל

יהי [math]\displaystyle{ G=(V\cup U,E) }[/math] גרף דו-צדדי. הוכיחו שאם [math]\displaystyle{ |E| }[/math] מס' אי-זוגי אז אין ב-[math]\displaystyle{ G }[/math] מעגל אוילר.

פתרון

נשים לב שבגרף דו צדדי מתקיים: [math]\displaystyle{ \underset{v\in V}{\sum}\deg{v}=|E|=\underset{u\in U}{\sum}\deg{u} }[/math], וזאת כיון שכל קשת יוצאת מצד אחד ומגיעה לצד השני, ולכן אם נספור את דרגות הקודקודים באחד הצדדים נקבל כל קשת (כי כל אחת חייב לעבור באחד הקודקודים בצד זה) בדיוק פעם אחת (כי לא יכול להיות ששתי קצוות הקשת באותו צד של הגרף). קיבלנו שסך דרגות הקודקודים בכל צד הוא אי-זוגי, ולכן בכל צד קיים קודקוד עם דרגה אי-זוגית, ובפרט אין מעגל אוילר.

נוסחת אוילר

תרגיל

יהי [math]\displaystyle{ G=(V,E) }[/math] גרף מישורי. נסמן: [math]\displaystyle{ v=|V|,e=|E| }[/math] (וכן נסמן את מס' התחומים בציור המישורי ב-[math]\displaystyle{ f }[/math]). נניח [math]\displaystyle{ v\geq 3 }[/math]. הוכיחו: [math]\displaystyle{ e\leq 3(v-2) }[/math].