Seja $v_a$ e $v_b$ vértices de um grafo $G$. A distância entre esses dois vértices, $d(v_a,v_b)$, é o comprimento do menor caminho entre eles em $G$. Ou seja, $min \{|P|: P = v_{a}$…$v_b\}$. Se tal caminho não existir,definimos $d(v_a,v_b) := \infty$.