10.2 Alapfogalmak, jelölések
Legyen V elemeknek egy véges halmaza, és E a V elemeiből képezett rendezett párok -esetleg üres - halmaza. Gráfnak nevezzük a V és E által meghatározott struktúrát. Jelölése: G(V,E). A V = {v1, v2, ... , vn} halmazt nevezzük a G gráf csúcshalmazának, jelölése V(G).

1. ábra. Példa egy G(V,E) gráfra.
V(G) elemeinek a számát a gráf rendjének nevezzük. Jelölése: n(G). E(G) elemeinek a számát a gráf méretének nevezzük. Jelölése: m(G). Az n-ed rendű, m méretű gráfot G(n,m) vagy Gn,m jelöli. Azt mondjuk, hogy e1 = {v1,v2} összeköti a v1 és v2 csúcsokat, v2 és v3 szomszédos csúcsok, e2 és e5 szomszédos élek és e4 és v6 illeszkednek.
Egy G gráf mindig leírható mátrixokkal. A szomszédsági mátrix A(G) = [aij]nxn ahol
Az illeszkedési mátrix B(G) = [bij]nxm ahol
Az 1. ábrán bemutatott gráf szomszédsági és illeszkedési mátrixa:

deg v = 1.
A v csúccsal szomszédos csúcsok halmazát Γ(v)-vel jelöljük. Világos, hogy degGv=|Γ(v)|.
a G gráf minimális, ill. maximális fokszáma:
A gráfelmélet segítségével könnyen megválaszolható az alábbi - rejtvényekben gyakran előforduló - kérdés: ha egy fogadáson n résztvevő van, és ezek közül m meghívott ismeri egymást, akkor hány kézfogás történik a kölcsönös üdvözléskor?
Tétel 10.1 ("Kézfogási" Lemma): Tekintsük a G(n,m)
gráfot, ahol . Ekkor
A tétel bizonyítása azonnal következik abból a tényből, hogy minden él pontosan két csúcsra illeszkedik.
Következmény.
Bármely gráfban a páratlan csúcsok száma mindig páros.