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

בגרף לא מכוון, אם יש קשתות שמחברות בין כל זוג קודקודים, אז הוא תמיד קשיר.

גרף מכוון שבו n קודקודים ויותר מ- n-1 קשתות, תמיד מכיל מעגל.

בגרף מכוון G שבו n קודקודים ו-m קשתות, אם m < n-1 אז הגרף תמיד קשיר.

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

יער הוא גרף שאין בו מעגלים, והוא בהכרח לא קשיר.

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

גרף מכוון G שבו הדרגות של כל הקודקודים גדולות מ-0 הוא תמיד קשיר.