Γράφος: Διαφορά μεταξύ των αναθεωρήσεων

Στην πιο κοινή έννοια του όρου,<ref>Δες για παράδειγμα, Iyanaga and Kawada, '''69 J''', p. 234 or Biggs, p. 4.</ref> έναςένα γράφοςγράφημα είναι ένα διατεταγμένο ζεύγος ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') αποτελούμενο από ένα σύνολο ''V'' των κορυφών ή κόμβων μαζί με ''E'' σύνολο από ακμές ή γραμμές, οι οποίες είναι υποσύνολα δύο στοιχείων ''V'' (δηλαδή, μια ακμή σχετίζεται με δύο κορυφές και η σχέση απεικονίζεται ως μη ταξινομημένο ζεύγος των κορυφών σε σχέση με τη συγκεκριμένη ακμή). Για να αποφευχθούν οι αμφισημίες, αυτός ο τύπος γραφήματος μπορεί να περιγραφεί με ακρίβεια ως μη-κατευθυνόμενο και απλό.

Οι κορυφές που ανήκουν σε μια ακμή ονομάζονται τελικά σημεία ή τελικές κορυφέςάκρα της ακμής. Μια κορυφή μπορεί να υπάρχει σε ένα γράφο και να μην ανήκει σε ακμή.

''V'' και ''Ε'' συνήθως λαμβάνονται υπόψην για ένα πεπερασμένο σύνολο, και πολλά από τα γνωστά αποτελέσματα δεν είναι αληθινά (ή είναι αρκετά διαφορετικά) για άπειρα γραφήματα, επειδή πολλά από τα επιχειρήματα αποτυγχάνουν σε άπειρες καταστάσεις. Η σειράτάξη ενός γραφήματος είναι <math>|V|</math> (ο αριθμός των κορυφών). Το μέγεθος ενός γραφήματος είναι <math>|E|</math>, ο αριθμός των ακμών. Ο βαθμός ενός κόμβου είναι ο αριθμός των ακμών που συνδέονται με αυτόν, όπου μια ακμή η οποία συνδέεται με την κορυφή και στα δύο άκρα (ένας βρόχος) συνυπολογίζεται δύο φορές.