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

1.	האם ייתכן גרף דו-צדדי פשוט שיש בו 8 קודקודים ו – 17 קשתות?

2.	נתון גרף מישורי קשיר שכל הקודקודים בו מדרגה 4 וכל פאה היא משולש או מרובע. מה מספר המשולשים?

3.	הראה כי לכל גרף פשוט G יש תת-גרף  H, שכולל את כל קודקודי  G, שהוא דו-צדדי, וכן מתקיים שמספר הקשתות ב-H  הוא לפחות מחצית ממספר הקשתות ב-G.

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

5.	נתונים שני גרפים מישוריים פשוטים  ו -, בעלי אותה קבוצות קודקודים . איחוד שני הגרפים הוא הגרף , שקבוצות הקשתות שלו היא האיחוד . 
	א. הוכח כי בכל תת-גרף של  קיים קודקוד בדרגה לכל היותר 11.   
	ב. הוכח כי מספר הצביעה של  הוא לכל היותר 12. 

6.	נתונים שני גרפים פשוטים  ו -, בעלי אותה קבוצות קודקודים . נתון כי  הוא גרף דו-צדדי מישורי ו- הוא עץ.
	א. הוכח  ש- הוא 2-צביע.
	ב. הוכח ש- הוא 2-צביע.
	ג. הוכח שהאיחוד של  ו- הוא 4-צביע.
	ד. האם  בהכרח מישורי?
	ה. האם האיחוד של  ו- בהכרח גרף מישורי?

7.	הוכיחו כי אם בגרף קשיר דרגות כל הקודקודים הן 4, אז ניתן לצבוע את קשתות הגרף בשני צבעים כך שכל קודקוד יהיה קצה של בדיוק 2 קשתות בכל אחד מהצבעים.

			בהצלחה