Dê exemplo de dois Grafos unicursais e dois não unicursais. Justifique que seus desenhos são dos tipos escolhidos.

Passo 1

O enunciado pede para dar exemplos de dois grafos unicursais (isto é, que admitem um trajeto que percorre todas as arestas sem repeti-las e sem levantar o lápis) e dois grafos não unicursais, justificando cada caso. O critério teórico é o seguinte: num grafo conexo existe um trajeto unicursal se, e somente se, o número de vértices de grau ímpar for 0 ou 2. Se for 0, há circuito euleriano; se for 2, há trilha que não fecha; caso contrário, não há trilha unicursal.

Passo 2

Exemplo 1 (unicursal com circuito): o ciclo C_4 com vértices \{v_1,v_2,v_3,v_4\} e arestas \{v_1v_2,v_2v_3,v_3v_4,v_4v_1\}.
Em cada vértice \deg(v_i)=2, que é par. Como o grafo é conexo e todos os graus são pares, existe circuito euleriano e, portanto, é unicursal.

Passo 3

Exemplo 2 (unicursal sem circuito): o caminho P_5 com vértices \{u_1,u_2,u_3,u_4,u_5\} e arestas \{u_1u_2,u_2u_3,u_3u_4,u_4u_5\}.
Aqui \deg(u_1)=\deg(u_5)=1 (ímpar) e \deg(u_2)=\deg(u_3)=\deg(u_4)=2 (pares). Há exatamente 2 vértices de grau ímpar e o grafo é conexo, logo existe trilha euleriana que une u_1 a u_5, e o grafo é unicursal.

Passo 4

Exemplo 3 (não unicursal): a estrela K_{1,3} com centro w e folhas \{x,y,z\}, arestas \{wx,wy,wz\}.
Temos \deg(w)=3 e \deg(x)=\deg(y)=\deg(z)=1. São 4 vértices de grau ímpar (>2), portanto não existe trilha que percorra todas as arestas sem repeti-las, e o grafo não é unicursal.

Passo 5

Exemplo 4 (não unicursal): grafo desconexo formado por dois ciclos C_3 separados, digamos \{a,b,c\} com arestas ab,bc,ca e \{d,e,f\} com arestas de,ef,fd.
Cada componente é euleriana isoladamente, mas o grafo total é desconexo e não há como traçar um único trajeto que cubra arestas de ambas, logo não é unicursal.

Resposta

  1. Ciclo C_4 — unicursal (graus todos pares).
  2. Caminho P_5 — unicursal (exatamente 2 vértices ímpares).
  3. Estrela K_{1,3} — não unicursal (4 vértices ímpares).
  4. Dois ciclos C_3 desconexos — não unicursal (grafo não conectado).

Exercícios relacionados