Grejaus kodai – tai taip sugeneruotos poaibes, kai bet kokios dvi gretimos poaibes skiriasi 1 elementu
Pilnas grafas – tai toks grafas, kurio virsunes sujungtos su visomis kitomis to grafo virsunemis.
Tuscias grafas – tai grafas turintis n virsuniu ir neturintis briaunu.
Dvipusis grafas tai toks grafas kurio virsunes galima isskaidyti i du poaibius A ir B taip, kad kiekvienos grafo briaunos galai priklausytu skiritingiems poaibiams.
Multi grafas – tai toks grafas turintis bent viena virsuniu pora sujungta keliom briaunom.
Grafas G yra plokstusis, jei ji galima pavaizduoti plokstumoje taip, kad jo briaunos kirstusi tiktai virsunese.
Medis – tai jungusis grafas neturintis ciklu.
1. Jei grafas yra medis, tai bet kurias dvi jo virsunes jungia vienas ir tik vienas kelias.
2. Visos medzio briaunos yra tiltai.
3. N virsuniu medis turi N-1 briauna.
4. Jungusis N virsuniu ir N-1 briaunos grafas yra medis.
Grafo jungianciuju medziu vadinamas toks medis kuris jungia visas pradinio grafo virsunes ir jo briaunos yra grafo briaunos.
Jei G yra jungusis svorinis grafas, tai tarp visu grafo G jungianciuju medziu yra vienas arba keli, kurio bendrasis svoris yra maziausias. Toks grafas vadinamas grafo G minimaliuoju jungianciuoju medziu.