מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/עצים/תרגילים/הגדרות שקולות לעץ/שאלה

נתון גרף לא-מכוון $\displaystyle G=(V,E)$. להלן שלוש תכונות:

1. $\displaystyle G$ קשיר.
2. $\displaystyle G$ חסר מעגלים.
3. $\displaystyle |E|=|V|-1$.

אנא הוכח שכל שתיים משלוש התכונות בהכרח גוררת את התכונה הנותרת.

רמז לגרירה $\displaystyle 1\wedge 3\rightarrow 2$ נניח בשלילה ש1 ו3 מתקיימים, אך יש מעגל. הסבר מדוע בפשטות לא ייתכן שהמעגל כולל את כל הצמתים. נניח שהמעגל אינו כולל את כל הצמתים. חשוב מה יקרה כשנוסיף לגרף, מעבר למעגל, עוד צמתים וקשתות.