שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2012 - גרפים

$F$ הוא יער ובו עשרה רכיבי קשירות. $G$ מתקבל מ-$F$ ע"י הוספת 9 צלעות חדשות ללא הוספת קודקודים. ליד כל אחת מהאפשרויות מסמו הקיפו בעיגול את אחד מהביטויים: תמיד / לעולם לא / לפעמים. ג. $G$ אינו קשיר ואין בו מעגלים.

רמז: אם $G$ לא קשיר, אז חלק מ-9 הצלעות לא שימשו לחיבור רכיבים - מה זה אומר על מעגלים?

פתרון: **לעולם לא.** אם $G$ אינו קשיר, אז לפחות צלע אחת "התבזבזה" על יצירת מעגל בתוך רכיב קיים (כי 9 צלעות לא הספיקו לחבר את כל 10 הרכיבים). לכן **אם $G$ אינו קשיר, בהכרח יש בו מעגלים**. לא ייתכן ש-$G$ גם לא קשיר וגם ללא מעגלים. $\blacksquare$