ניתוח טענות גרפים ועץ פורש מקסימלי

בשאלה זו שני סעיפים, א-ב, שאין קשר ביניהם. ענו על שני הסעיפים.

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

1. לכל עץ פורש DFS של אותו גרף G לא מכוון יש תמיד אותו מספר עלים.
2. גובה עץ פורש BFS של גרף G לא מכוון, תמיד קטן או שווה לגובה עץ פורש DFS של אותו הגרף.
3. גרף G לא מכוון בעל n צמתים ו־ n-2 קשתות הוא תמיד לא קשיר.
4. בכל גרף G מכוון שבו n צמתים ו־ m >= n קיים מעגל.
5. גרף G לא מכוון שבו הדרגות של כל הקודקודים גדולות מ־ 0 הוא תמיד קשיר.

"עץ פורש מקסימלי" הוא עץ פורש של גרף G לא מכוון שבו סכום ערכי הקשתות הוא מקסימלי. כתבו אלגוריתם המוצא בגרף G "עץ פורש מקסימלי".