De
graad (of
valentie) van een knoop in een
graaf is het aantal buren van die knoop. In een niet-gerichte graaf is dit het aantal bogen dat in de knoop samenkomt. Voor een gerichte
graaf maken we onderscheid tussen de inkomende en de uitgaande graad, respectievelijk het aantal bogen dat toekomt en het aantal bogen dat vertrekt in deze knoop.