Προτάσεις σε συνεκτικούς μη κυκλικούς γράφους

Οι παρακάτω προτάσεις είναι ισοδύναμες για πεπερασμένους γράφους με ν > 0 κόμβους:
  1. Ο γράφος Γ είναι συνεκτικός και μη κυκλικός.
  2. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
  3. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
  4. Ο γράφος είναι μη κυκλικός και περιέχει ν - 1 ακμές.
  5. Ο γράφος είναι συνεκτικός και περιέχει ν - 1 ακμές.