Naj bo $V$ (običajno končna) neprazna množica in $E$ poljubna družina dvoelementnih podmnožic množice $V$. Paru $\Gamma = (V,E)$ pravimo graf na množici točk (tudi vozlišč) $V = V(\Gamma)$ in z množico povezav $E = E(\Gamma)$. Če je $\{u,v\}$ povezava grafa $\Gamma$, tedaj pravimo, da sta točki $u$ in $v$ sosednji in pišemo $u \sim v$. Hkrati pravimo, da sta točki $u$ in $v$ krajišči povezave $\{u,v\}$. Povezavo $\{u,v\}$ včasih pišemo krajše kot $uv$ ali $vu$.

OPOMBA
Včasih dopuščamo tudi grafe, ki imajo med nekaterimi pari točk več povezav (vzporedne povezave) ali pa imajo povezave, ki imajo obe krajišči enaki (zanke). Takim grafom bomo rekli multigrafi. Če definiramo, da zanka prispeva $2$ k stopnji točke, potem lema 1.1 velja tudi za multigrafe. Kadar želimo poudariti, da govorimo o (multi)grafih brez zank in vzporednih povezav, takim grafom rečemo enostavni grafi.

Poleg multigrafov je grafom sorodna stuktura usmerjeni graf. Neformalno si ga lahko predstavljamo kot graf (ali celo kot multigraf), kjer vsako povezavo usmerimo. Namesto krajišč povezave v tem primeru govorimo kot o začetku in koncu povezave (repu in glavi povezave).
Grafe si radi tudi narišemo. To storimo tako, da vozlišča grafa predstavimo kot točke ravnine, povezavo med sosednjima vozliščema pa kot krivuljo (običajno kar kot daljico) s krajiščema v točkah ravnine, ki ustrezata krajiščema povezave.
Stopnja točke (tudi valenca točke) $u$ v grafu $\Gamma$, označimo jo z $deg_{\Gamma}(u)$, je enaka številu povezav grafa $\Gamma$, ki imajo točko $u$ za svoje krajišče. Točkam stopnje $0$ pravimo izolirane točke. Graf $\Gamma$ je regularen, če obstaja tako število $k$, da velja $deg_{\Gamma}(u) = k$ za vsak $u \in V(\Gamma)$. V tem primeru rečemo tudi, da je graf $\Gamma$ $k$-regularen, oziroma, da je regularen stopnje $k$.

Stopnje točk in število povezav grafa veže naslednja enakost:

Dokaz

POSLEDICA 7.2
Vsak graf ima sodo mnogo točk lihe stopnje.

Graf $\Gamma'$ je podgraf grafa $\Gamma$, če velja $V(\Gamma') \subseteq V(\Gamma)$ in $E(\Gamma') \subseteq E(\Gamma)$. Podgraf $\Gamma'$ je vpet, če velja $V(\Gamma') = V(\Gamma)$, in je induciran z množico točk $U \subseteq V(\Gamma)$, če velja $V(\Gamma') = U$ in $E(\Gamma') = \{uv \in E(G) \mid u,v \in V(H)\}$. V tem primeru pišemo tudi $\Gamma' = \Gamma [U]$.
Graf $\Gamma$ je dvodelen, če lahko množico točk $V(\Gamma)$ zapišemo kot disjunktno unijo dveh podmnožic $A,B \subseteq V(\Gamma)$ tako, da je za vsako povezavo $uv \in E(\Gamma)$ ena od točk $u,v$ vsebovana v množici $A$, druga pa v množici $B$. Množici $A$ in $B$ imenujemo množici dvodelnega razbitja grafa $\Gamma$.

Zaporedje točk $v_0v_1...v_k$ grafa $\Gamma$ je sprehod dolžine $k$, če $v_i \sim v_{i+1}$ za $0 \le i < k$. Sprehod je enostaven, če so vse povezave na njem različne. Sprehod je sklenjen, če je $v_0 = v_k$. Sprehod, na katerem so vse točke različne, je pot, enostaven sklenjen sprehod z vsaj eno povezavo, na katerem sta enaki le prva in zadnja točka, pa je cikel grafa. Zradi enostavnosti dopuščamo tudi sprehode dolžine $0$, tj. sprehode oblike $v_0$. Sprehod dolžine $0$ je seveda hkrati tudi pot, domenimo pa še, da ga ne bomo imeli za cikel.

Dokaz

Za dve točki $u$ in $v$ rečemo, da sta v isti povezani komponenti, če med njima obstaja sprehod. Ni težko videti, da je relacija “biti v isti povezani komponenti” ekvivalenčna. Njenim ekvivalenčnim razredom rečemo povezane komponente grafa. Graf je povezan, če ima eno samo povezano komponento.
Razdaljo $d_{\Gamma}(u,v)$ med točkama $u$ in $v$ v grafu $\Gamma$ definiramo kot dolžino najkrajše poti od $u$ do $v$ v $\Gamma$. (Če taka pot ne obstaja, za razdaljo vzamemo vrednost $\infty$.) Kot pove lema 1.3, bi lahko razdaljo ekvivalentno definirali tudi kot dolžino najkrajšega sprehoda med danima točkama.
S tako definirano razdaljo postane množica točk povezanega grafa metrični prostor. Največji razdalji med parom točk grafa pravimo premer (tudi diameter) grafa,

Dolžini najkrajšega cikla v grafu pravimo tudi notranji obseg (ali ožina) grafa.

Polni grafi $K_n: V(K_n) = \mathbb{Z}_n$, $E(K_n) = \{uv \mid u,v \in \mathbb{Z}_n, u \ne v\}$. Polni graf $K_n$ ima $n$ točk in ${n \choose 2} = \frac{n(n-1)}{2}$ povezav. Je $(n-1)$-regularen graf in je dvodelen le za $n = 1$ in $2$.

Poti $P_n: V(P_n) = \mathbb{Z}_n$, $E(P_n) = \{u(u+1) \mid u = 0,1,...,n-2\}$. Pot $P_n$ ima $n$ točk in $n-1$ povezav (njena dolžina je $n-1$). Za $n = 1$ in $n = 2$ je enaka grafu $K_n$, za $n \ge 3$ pa velja $\delta(P_n) = 1$ in $\Delta(P_n) = 2$. Vse poti so dvodelni grafi.

Cikli $C_n (n \ge 3): V(C_n) = \mathbb{Z}_n$, $E(C_n) = \{u(u + 1) \mid u \in \mathbb{Z}_n\}$. Kadar dopuščamo tudi multigrafe, sta definirana še cikla $C_1$ (zanka) in $C_2$ (par vzporednih povezav).

Cikel $C_n$ ima $n$ točk in $n$ povezav. Je $2$-regularen graf in je dvodelen natanko tedaj, ko je $n$ sodo število. Vsak $2$-regularen graf je disjunktna unija enega ali več ciklov. Cikel $C_3$ imenujemo tudi trikotnik.

Polni dvodelni grafi $K_{m,n}: V(K_{m,n}) = A \cup B$, kjer velja $\mid A \mid = m$, $\mid B \mid = n$ in $A \cap B = \emptyset$, $E(K_{m,n}) = \{uv \mid u \in A, v \in B\}$. Polni dvodelni graf $K_{m,n}$ ima $m+n$ točk in $mn$ povezav. Zanj velja $\delta (K_{m,n}) = min\{m,n\}$ in $\Delta (K_{m,n}) = max\{m,n\}$. Graf $K_{m,n}$ je regularen natanko tedaj, ko je $m = n$. Vsi grafi $K_{m,n}$ so dvodelni. Grafom $K_{1,n}$ pravimo tudi zvezde.

Hiperkocke $Q_d: V(Q_d) = \{(u_1,u_2,...,u_d) \mid u_i \in \{0,1\}\}$, $E(Q_n) = \{uv \mid u,v \in V(Q_d) : \sum^d_{i=1} \mid u_i - v_i \mid = 1\}$. Običajno med hiperkocke štejemo tudi $0$-razsežno kocko $Q_0 = K_1$. Hiperkocka $Q_d$ (skelet $d$-razsežne kocke) ima $2^d$ točk in $d \cdot 2^{d-1}$ povezav. Je $d$-regularen graf. Vse hiperkocke so dvodelni grafi (za množici dvodelnega razbitja vzamemo množico točk, ki imajo sodo mnogo komponent enakih $0$, in množico točk, ki imajo liho mnogo komponent enakih $0$).

Kolesa $W_n (n \ge 3): V(W_n) = \mathbb{Z}_n \cup \{\infty \}$, $E(W_n) =\{u(u+1),u \infty \mid u \in \mathbb{Z}_n \}$. Graf $W_n$ ima $n + 1$ točk in $2n$ povezav. Za kolesa velja $\delta (W_n) = 3$ in $\Delta(W_n) = n$.

Edino regularno kolo je $W_3 \simeq K_4$. Nobeno kolo ni dvodelen graf.

Posplošeni Petersenovi grafi $P_{n,k} (n \ge 3$ in $0 < k < n): V(P_{n,k}) = \{u_i,v_i \mid i \in \mathbb{Z}_n \}$, $E(P_{n,k}) = \{u_iu_{i+1},u_iv_i,v_iv_{i+k} \mid i \in \mathbb{Z}_n \}$. Posplošeni Petersenov graf $P_{n,k}$ ima $2n$ točk. Če je $n \ne 2k$, ima $3n$ povezav in je kubičen graf, za $n = 2k$ pa ima $\frac{5n}{2}$ povezav in velja $\delta (P_{n,k}) = 2$, $\Delta (P_{n,k})= 3$. Graf $P_{n,k}$ je dvodelen natanko tedaj, ko je število $n$ sodo in število $k$ liho. Družina ima ime po Petersenovem grafu $P_{5,2}$.

Krožni grafi $Cir(n;S)$: Naj bo $S$ poljubna podmnožica grupe $\mathbb{Z}_n$, ki ne vsebuje elementa $0$ in ki z vsakim elementom $s \in S$ vsebuje tudi nasprotni element $n-s$. Krožni graf $\Gamma = Cir(n;S)$ na $n$ točkah in s simbolom $S$ je določen takole:

Med krožne grafe spadajo polni grafi in cikli: $K_n = Cir(n;\{1,2,...,n-1\})$ in $C_n = Cir(n;\{1,n-1\})$.
Krožni graf $Cir(n;S)$ ima $n$ točk in $\frac{n \mid S \mid}{2}$ povezav. Je $\mid S \mid$-regularen graf. Naj bo $S = \{s_1,...,s_d\}$, kjer je $d \ge 1$. Če je $gcd(n,s_1,...,s_d) = 1$, potem je krožni graf $Cir(n;S)$ dvodelen natanko tedaj, ko je število $n$ sodo, vsa števila $s_i, 1 \le i \le d$, pa so liha.

Cayleyjevi grafi $Cay(G;S)$: Cayleyjevi grafi so posplošitev krožnih grafov. Naj bo $G$ končna grupa in $S$ poljubna podmnožica grupe $G$, ki ne vsebuje enote grupe $G$ in ki z vsakim elementom $s \in S$ vsebuje tudi nasprotni element $s^{-1}$. Cayleyjev graf $\Gamma = Cay(G;S)$ grupe $G$ in s simbolom $S$ je določen takole:

Med cayleyjeve grafe spadajo tudi hiperkocke, saj lahko graf $Q_d$ predstavimo kot cayleyjev graf grupe $\mathbb{Z}^d_2$ s simbolom $S = \{(1,0,...,0),(0,1,...,0),...,(0,0,...,1)\}$. Cayleyjevi grafi so $\mid S \mid$-regularni grafi.