Definição: Passeio

Dado um grafo $G=(V, A)$, um passeio em $G$ consiste de uma sequência finita alternada de vértices e arestas, começando e terminando por vértices, tal que cada aresta é incidente ao vértice que a precede e ao que a sucede.

Matematematicamente, temos que um passeio em $G$ é uma sequência não vazia $P = (v_0,a_0,v_1,a_1,\cdots,a_{k-1},v_k)$ de vértices ($v_k$) e arestas ($e_k$) de $G$, em que $a_i=\{v_i,v_{i+1}\}$ para todo $i<k$.

Os vértices $v_0$ e $v_k$ são a origem e o término de $P$, respectivamente, ou também chamados de extremidades. Além disso, os vértices $v_1,v_2,\dots,v_{k-1}$ são os vértices internos de $P$.

O comprimento de um passeio é o número de arestas de $P$, e denota-se $P^k$., onde $k$ é o comprimento de $P$.

Se $v_0=v_k$, o passeio é fechado.

Definição: Trajeto

Dado um grafo $G(V, A)$, um trajeto em $G$ consiste em um passeio, tal que cada aresta aparece apenas uma vez. Um trajeto no qual o vértice inicial e o final são iguais é chamado de trajeto fechado.

Definição

Dado um grafo $G(V, A)$, um caminho em $G$ consiste em um passeio onde não há repetições de vértices,isto é, eles são todos distintos.

Em outras palavras, um caminho é um trajeto onde não há repetição de vértices.

Definição

Um trajeto fechado no qual nenhum vértice (com exceção do inicial e do final) aparece mais de uma vez é chamado de ciclo (circuito ou caminho fechado).

O compriemnto de um ciclo é dado pelo seu número de arestas. O ciclo de tamanho $k$ é chamado de $k$-ciclo e denotado por $C^k$.

Um ciclo é simples se não tem vértices repetidos exceto pelo último, que coincide com o primeiro.

Proposição

Se $G(V,A)$ é um grafo tal que $d(v) \geq 2$ para todo $v \in V$, então $G$ contém um ciclo.

Demonstração:

Se $G$ possui laços ou arestas paralelas, não há o que provar. Então, vamos supor que $G$ é um grafo simples. Seja $v_0 \in V$ um vértice arbitrário de $G$. Como $d(v) \geq 2$ para todo $v \in V$, podemos construir um passeio $v_0 \to v_1 \to v_2 \cdots$ indutivamente, escolhendo $v_{i+1}$ como sendo qualquer vértice adjacente a $v_i$ exceto $v_{i-1}$.

Como $G$ possui uma quantidade finita de vértices, em algum momento escolheremos algum vértice, digamos $v_k$, pela segunda vez.

A parte do passeio entre a primeira e a segunda ocorrência de $v_k$ constitui um ciclo.

$\square$