Két gráfot izomorfnak nevezünk, ha pontjaik és éleik kölcsönösen egyértelműen és illeszkedéstartóan megfeleltethetők egymásnak.

Egy gráf olyan élét, amelynek végpontjai azonosak, hurokélnek nevezzük.

Az ED, DG, GL, … egymáshoz csatlakozó élek sorozatát sétának nevezzük, ebben az esetben az élek és pontok nem feltétlenül különbözőek, ha két pont között séta van, akkor minden esetben út is van.

Ha egy gráfban két pontot több él is összeköt, akkor ezeket az éleket többszörös éleknek vagy párhuzamos éleknek nevezzük.

A gráf egy pontjába összefutó élek számát a pont fokszámának (röviden fokának) nevezzük.

Bármely gráfban a fokszámok összege az élek számának kétszerese, valamint bármely gráfban a páratlan fokszámú pontok száma páros.

Bármely véges vagy végtelen térkép (amelyen szomszédos országok más-más színnel vannak jelölve) kiszínezhető négy színnel.

Olyan összefüggő gráf, amelyben nincs kör.

Ha egy gráfnak van Euler-vonala, az azt jelenti, hogy a gráf egyik pontjából kiindulva a ceruza felemelése nélkül megrajzolhatjuk a gráfot úgy, hogy ceruzánkkal minden élen pontosan egyszer haladunk át, és visszatérünk a kiindulópontba.

Körnek nevezzük a kezdőpontjába visszatérő utat, azaz minden olyan élsorozatot, amely kezdőpontjába tér vissza, és minden pont és minden él csak egyszer szerepelt. Ha egy gráfban nincs kör, akkor azt a gráfot körmentes gráfnak nevezzük. A maximális körmentes összefüggő gráf a fa, hiszen akármelyik két pontját kötnénk is össze, amely eddig nem volt összekötve, akkor a gráfban már lenne kör.

Olyan gráf, amelynek nincs izolált pontja, tehát amely bármely pontjából bármely másik pontjába élek egymásutánja mentén el lehet jutni.

A gráfelméletben a kör élek olyan egymáshoz csatlakozó sorozata, amelyben az élek és pontok egynél többször nem szerepelhetnek, és a kiindulási pont megegyezik a végponttal.

Euler vetette fel a problémát: lehet-e Königsberg (más néven Kalinyingrád) városán átfolyó Pregel folyó hídjain keresztül olyan sétát tenni, hogy ennek során minden hídon pontosan egyszer haladjunk át? A kérdésre a válasz nemleges. A königsbergi hidak problémája adta az első indítást a gráfelmélet felépítéséhez.

Gráfnak nevezzük pontoknak és éleknek egy halmazát, ahol élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik.

Az n elemű halmaz k elemű részhalmazait az n elem k-ad osztályú ismétlés nélküli kombinációinak nevezzük. Ezek jelölése: . N elem k-ad osztályú ismétlés nélküli kombinációinak száma : . Például 8 sportoló közül az edző 3-at küld versenyre. A 8 ember közül összesen féle képen választhatja ki a három embert.

Ha egy n elemű halmazból úgy képezünk k hosszúságú elemsorozatokat, hogy azok sorrendje is fontos és egy elem többször is szerepelhet, akkor az ilyen kiválasztásokat és rendezéseket ismétléses variációnak nevezzük. Ezek száma: .

N elem, melyből n₁, n₂ … n_k egyforma van, lehetséges sorrendjeit az eleme ismétléses permutációjának hívjuk. Ezek száma:

A kéttagú kifejezést idegen szóval binomnak nevezzük. A binomok hatványozásánál fellépő együtthatóknak innen származik az elnevezése. Az (n¦k) számokat binomiális együtthatóknak nevezzük. Az n és k természetes számok, a k nem lehet nagyobb az n-nél.

Ha egy n elemű halmaz elemiből úgy képezünk k hosszúságú elemsorozatokat, hogy azok sorrendje is fontos és minden elemet csak egyszer választunk ki, akkor ezt variálásnak mondjuk. Az így kapott elemsorozatokat variációknak nevezzük. Ezek száma: . Például hányféle képen lehet 8 színből kiválasztott három színnel kiszínezni egy háromszínű zászlót készíteni? Összesen = 336 lehetőség van.

; ; ;

Legyen n számú egymástól különböző elemünk. Ezekből tetszőlegesen választott k (k n) különböző elem egy meghatározott sorrendjét az n elem k-adosztályú ismétlés nélküli variációjának nevezzük. Az n egymástól különböző elem összes k-adosztályú variációjinak száma: . Ha a kiválasztáskor ugyanaz az elem többször is szerepelhet és az elemek sorrendjét is figyelembe vesszük, akkor az n elem k-adosztályú ismétléses variációját kapjuk. Ezeknek száma: n^k.

Variáció a kombinatorikában használt fogalom. A variáció lehet ismétléses és ismétlés nélküli. Van egy halmazunk n elemszámmal. A halmazból kiválasztunk elemeket és sorba rakjuk őket ez egy variáció. Ha a halmazból k elemet választunk ki, akkor ezt k-ad osztályú variációról beszélünk. Ismétléses variáció a következő: V=n^k , szóban: Az n elem k-ad osztályú ismétléses variációinak száma. Ismétlés nélküli variáció: V =n!/(n-k)! , szóban: Az n elem k-ad osztályú ismétlés nélküli variációinak száma Vi.