Caminhos internamente disjuntos: Dois caminhos entre u e v são internamente disjuntos se eles não possuem nenhum vértice interno em comum.
Teorema 4.2.2 (Whitney): Um grafo G que possui pelo menos 3 vértices é 2-conexo se e somente se para cada par u,v em V(G) existem caminhos internamente disjuntos entre u e v.
Orelha: Uma orelha de um grafo G é um caminho maximal cujos vértices internos têm grau 2 em G.
Decomposição em orelhas: Uma decomposição em orelhas de um grafo G é uma decomposição P0, ... Pk tal que P0 é um ciclo e Pi para i >1 é uma orelha de P0 unido com P1 ... unido com Pi .
Exemplo:
Teorema 4.2.8 (Whitney): Um grafo é 2-conexo se e somente se ele possui uma decomposição em orelhas.
Teorema 4.2.17 (Menger): Se x, y são vértices de um grafo G e xy não está em E(G), então o tamanho mínimo de um x,y - corte é igual ao número máximo de caminhos internamente disjuntos entre x e y.
Grafo Linha: O grafo linha de um grafo G, chamado de L(G), é o grafo cujos vértices são as arestas de G, com ef Î E(L(G)) quando e = uv e f = vw em G.
Exemplo:
