Προσπαθήσαμε και συγκεντρώσουμε ορισμούς για  τα περισσότερα από  τα είδη γράφων καθώς και χρήσιμα πορίσματα που προκύπτουν. 

 Είδη γράφων 

1. Πλήρης Γράφος ή Κλίκα 

Ένας πλήρης γράφος ή κλίκα είναι ένας απλός γράφος G που για τον οποίον κάθε ζεύγος κορυφών του συνδέετε με ακμή.
Ο πλήρης γράφος συμβολίζεται με Κn όπου n το σύνολο των κορυφών του. 


2. Διμερής Γράφος

Ένας γράφος G είναι διμερής αν το σύνολο των κορυφών του V(G) είναι ένωση δύο ξένων μεταξύ τους συνόλων V1(G) V2(G) τέτοια ώστε κάθε ακμή να εφάπτεται σε μια κορυφή του V1 και σε μια του V2.

3. Πλήρης Διμερής ή Διχοτομίσιμο γράφημα

Ένας πλήρης διχοτομίσιμος γράφος είναι αν το σύνολο των κορυφών του διαμερίζεται σε δύο υποσύνολα V1 με n κορυφές και V2 με m κορυφές τέτοια ώστε για κάθε ζεύγος κορυφών (n,m) υπάρχει ακμή που τις συνδέει. 
Ο πλήρης Διμερής συμβολίζεται με Κn,m.

4.Μονοπάτι 

Ως μονοπάτι Ρ μήκους ν είναι μια ακολουθία από ν+1 κορυφών όπου οι ακμές εναλλάσσονται των κορυφών  που ανήκουν στην ακολουθία.

5. Απλό Μονοπάτι

Καλείται το μονοπάτι δίχως επαναλαμβανόμενες κορυφές.

6. Κύκλος 

Είναι το μονοπάτι χωρίς επαναλαμβανόμενες ακμές και η αρχική και τελική κορυφή συμπίπτουν.

7.Απλός κύκλος 

Ένας κύκλος δίχως επαναλαμβανόμενες κορυφές με εξαίρεση της αρχικής και τελικής κορυφής.

8. Συνδεδεμένος Γράφος

Ένας γράφος G  είναι συνδεδεμένος αν για οποιοδήποτε ζεύγος κορυφών του(v,u) υπάρχει ένα μονοπάτι από την v στην u.

9.Βαθμός κορυφής 

Ο Βαθμός κορυφής u  σε ένα γράφο G τον συμβολίζουμε με d(u) και είναι ίσος με το άθροισμα του αριθμού των απλών ακμών που περιέχουν την κορυφή u και του διπλάσιου του αριθμού των loop που περιέχουν την u.

10. Μέγιστος Βαθμός γράφου

Ο μέγιστος βαθμός γράφου G  συμβολίζεται με ΔG είναι ο μέγιστος μεταξύ των βαθμών των κορυφών του γράφου. Ενώ ελάχιστος βαθμός δG είναι ο ελάχιστος βαθμός των κορυφών του γράφου G.

11.Σύνολο ανεξαρτησίας

Όταν αναφερόμαστε σε ανεξάρτητα μερίδια κορυφών ενός γράφου αναφερόμαστε ουσιαστικά σε ένα υποσύνολο των κορυφών του οι οποίες δεν συνδέονται με ακμή. Με άλλα λόγια μιλάμε για ανεξάρτητα σύνολα κορυφών ή πολύ πιο απλά για Σύνολα Ανεξαρτησίας.

12. Χρωματικός αριθμός γράφου

Είναι ο ελάχιστος αριθμός χ(G) συνόλων ανεξαρτησίας τα οποία διαμερίζουν το σύνολο κορυφών του G .

13. Επίπεδος Γράφος 

Ένας γράφος είναι επίπεδος αν δεν περιέχει  ακμές να τέμνονται.

Πορίσματα 

1. Σε κάθε κατευθυνόμενο γράφο αντιστοιχεί ένας μοναδικός μη -κατευθυνόμενος γράφος. Το αντίστροφο δεν ισχύει.

2. Ο Κn έχει n(n-1)/2 ακμές  

3. Ο Κn,m έχει n*m ακμές 

4.Ο χρωματικός αριθμός κάθε επίπεδου γράφου είναι το πολύ 4

5.Ένας γράφος είναι διμερής αν και μόνο αν δεν περιέχει περιττό κύκλο.

6. Κάθε γράφος έχει έναν άρτιο αριθμό κορυφών περιττού βαθμού.

7.Κάθε απλός γράφος με τουλάχιστον δύο κορυφές περιέχει δύο κορυφές ίσου βαθμού.

8. Μια κλίκα Κn έχει (n-1)!/2 κύκλους μήκους n.

9. Σε πλήρη διμερή γράφο Κn,n υπάρχουν n!(n-1)!/2 κύκλοι μήκους 2n.

10. Αν σε γράφο G τάξης n με δG=>n-1/2 τότε ο γράφος είναι συνδεδεμένος