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

ΑΠΟΔΕΙΞΗ:
Θα δείξουμε πρώτα ότι το G είναι συνεκτικό. Υποθέστε ότι το έχει δύο ή περισσότερες συνεκτικές συνιστώσες. Έστω u1 μια κορυφή σε μία συνιστώσα με n1 κορυφές και έστω u2 μια κορυφή σε μία άλλη συνιστώσα με n2 κορυφές.  Αφού ο βαθμός της u1 είναι το πολύ n1- 1  ο βαθμός της u2  είναι το πολύ n2-1, το άθροισμα των βαθμών τους είναι το πολύ  n1+n2-2, που είναι μικρότερο από n- 1, πράγμα που αντιφάσκει με την υπόθεση.

Θα δείξουμε τώρα πώς μπορεί να κατασκευαστεί ένα μονοπάτι Hamilton με μια βήμα προς βήμα διαδικασία, αρχίζοντας με ένα μονοπάτι το οποίo περιέχει μια μόνο ακμή. Έστω ότι υπάρχει ένα μονοπάτι p-1 ακμών στο G, με p < n, το οποίο συναντά την ακολουθία των κορυφών (u1,u2....up).
Αν είτε η  u1 είτε η up είναι γειτονική με μια κορυφή η οποία δεν είναι στο μονοπάτι, μπορούμε αμέσως να επεκτείνουμε το μονοπάτι έτσι ώστε αυτό να περιλάβει αυτή την κορυφή, δημιουργώντας έτσι ένα μονοπάτι  p  ακμών.
Διαφορετικά οι u1  και up είναι γειτονικές μόνο με κορυφές του μονοπατιού. 

Θέλουμε να δείξουμε ότι  στην περίπτωση αυτή υπάρχει ένα κύκλωμα το οποίο περιέχει  ακριβώς τις κορυφές (u1,u2....up). 
Αν η  u1 είναι γειτονική με την up, τότε το (u1,u2....up,u1) είναι ένα τέτοιο κύκλωμα. 
Ας υποθέσουμε τώρα ότι η u1 είναι γειτονική μόνο με τις ui1,ui2,....,uik όπου 2 <=ik<=p-1.
Αν η up είναι γειτονική με μία από τις ui1-1,ui2-1,....,uik-1  ας πούμε με τη uj-1 τότε το κύκλωμα (u1,u2....uj-1,up, up-1,...uj,u1) περιέχει ακριβώς τις κορυφές u1,u2....up.
Αν η up δεν είναι γειτονική με οποιαδήποτε από τις κορυφές ui1-1,ui2-1,....,uik-1 τότε η up είναι γειτονική με το πολύ p-k-1 κορυφές. 
Συνεπώς το άθροισμα των βαθμών των κορυφών των  u1  και up  είναι το πολύ n-2, πράγμα που αντιφάσκει με την υπόθεση.

Τώρα που έχουμε ένα κύκλο το οποίο περιέχει όλες τις κορυφές  u1,u2....up  ας επιλέξουμε την κορυφή ux η οποία δεν είναι στο κύκλωμα. Επειδή το G είναι συνεκτικό,υπάρχει μια κορυφή uk που ενώνεται με την ux μέσω μιας ακμής η οποία δεν είναι στο κύκλωμα, έστω uk .
Έχουμε τώρα το μονοπάτι (ux , uk , uk+1,....,uj-1, up , up-1,.... uj, u1,u2, ..., uk-1) το οποίο περιέχει p ακμές. Μπορούμε να επαναλάβουμε την διαδικασία μέχρι το σημείο του να έχουμε ένα μονοπάτι με n-1 ακμές.

Πρέπει όμως να επισημάνουμε ότι η συνθήκη δεν είναι αναγκαία για την ύπαρξη μονοπατιού Hamilton σε ένα γράφο. Για παράδειγμα σε ένα γράφο G n-γώνιο με n>5 είναι προφανές ότι περιέχει κύκλο Hamilton παρ' όλο που το άθροισμα των βαθμών οποιωνδήποτε δύο κορυφών είναι 4.