יהי T עץ סופי, לא מכוון, עם n\geq4 צמתים. הוכיחו כי התנאים הבאים שקולים:
-
קיימים ב-T לפחות 3 עלים.
-
קיים ב-T צומת שדרגתו לפחות 3.
הצלחתי להוכיח כי הטענה הראשונה גוררת את הטענה השנייה אבל אני לא מצליח להוכיח הפוך.
כיצד עלי לפתור את הבעיה?
נפריד לשלבים:
א. נוכיח A\to B: נניח כי קיימים ב-T לפחות 3 עלים ונוכיח כי קיים ב-T צומת שדרגתו לפחות 3. נתבונן במילת פרופר המתאימה לעץ. ידוע כי העץ מכיל n צמתים ולכן המילת פרופר המתאימה היא באורך n-2. כמו כן, ידוע כי העץ מכיל לפחות 3 עלים ולכן המילה המתאימה אינה מכילה לפחות 3 צמתים. נסמן את מספר האותיות במילה כיונים ואת מספר המקומות במילה כתאים ולכן ע"פ עקרון שובך היונים, נוכל להסיק כי קיים שובך עם לפחות \lceil\frac{n-3}{n-2}\rceil=2 יונים. כלומר קיימת אות שמופיעה לפחות פעמיים. ידוע כי כל צומת בעץ מופיעה במילת הפרופר המתאימה כדרגתה פחות 1. ולכן נוכל להסיק כי קיימת צומת שמופיעה לפחות 2+1=3 פעמיים.
ב. נוכיח B\to A: נניח כי קיים ב-T צומת שדרגתו לפחות 3 ונוכיח כי קיימים ב-T לפחות 3 עלים. נתבונן במילת פרופר המתאימה לעץ. ידוע כי העץ מכיל n צמתים ולכן המילת פרופר המתאימה היא באורך n-2. ידוע כי קיים צומת ב-T שדרגתו לפחות 3. ידוע כי כל צומת בעץ מופיעה במילת הפרופר המתאימה כדרגתה פחות 1. לכן, נוכל להסיק כי הצומת שדרגתה לפחות 3, מופיעה לפחות פעמיים במילת פרופר המילה. מכך, נובע כי שאר הצמתים מופיעים לכל היותר n-4 פעמיים. מאחר והגרף מכיל n צמתים (כאשר אחד מהם בעל דרגה לפחות 3), נוכל להסיק כי יש לפחות (n-1)-(n-4)=3 אותיות שלא מופיעות במילת פרופר. לכן יש לפחות 3 צמתים שלא מופיעים בעץ.
מקווה שמובן 