לפניכם חמש טענות. בחרו בארבע מהן.

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

אם ציינתם שהטענה נכונה - נמקו מדוע, ואם ציינתם שהטענה אינה נכונה, הביאו דוגמה נגדית או נמקו מדוע.

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

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