Title: תרגיל 12 – מתמטיקה בדידה
Author: SHAI
Last saved by: eladv
Company: Tel-Aviv University

תרגיל 14 – מתמטיקה בדידה
לא להגשה

1.	כמה רכיבי קשירות יש לגרף חסר מעגלים בן 17 קודקודים ו – 10 קשתות?

2.	הוכח כי אם בעץ קיים קודקוד מדרגה d אז קיימים בו d עלים.

3.	הוכיחו כי אם בגרף פשוט מתקיים לכל זוג קודקודים לא סמוכים  x, y: , אז הגרף קשיר.

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

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

6.	יהא  הגרף הבא:, , . מה מספר הצביעה של G?

7.	(שאלת רשות לחופש). סדרה באורך n נקראת סדרה גרפית אם קיים גרף שהסדרה היא סדרת הדרגות שלו. קרא את המאמר Realizability and uniqueness in graphs של Martin Aigner  ו- Eberhard Triesch שפורסם בז'ורנל Discrete Mathematics, Volume 136,  Issue 1-3, December 1994, Pages 3-20. סכמו את התנאים המספיקים והכרחיים לכך שסדרה תהיה גרפית. קראו והבינו את ההוכחה שלהם לתנאי ההכרחי והמספיק שניתן לראשונה ע"י Erdos  ו-Gallai.