Gabriel Borges, Lista 1 de MC558. 1s/2014.

1. Não sei.

2. Se existe um passeio de u a v, seja S a sequência alternada de vértices e arestas, começando em u e terminando em v. Então: ou S não apresenta vértices repetidos (e S já é um caminho), ou S apresenta vértices repetidos. Seja t o primeiro desses vértices (i.e., o primeiro vértice a aparecer pela segunda vez em S). Seja q o próximo vértice a aparecer na sequência depois da segunda aparição de t. Consideremos S: <u,...,t,...,t,e(t,q),q>. É garantido que o seguinte passeio também é possível: S': <u,...,t,e(t,q),q> (i.e., o trecho compreendido entre a primeira aparição de t (inclusive) e a segunda aparição de t (exclusive) em S foi suprimido). O passeio ainda é válido porque sabemos que existe uma aresta de t a q. Ao repetirmos esse passo novamente enquanto houver vértices repetidos, então chegaremos num passeio Sc que também é um caminho, pela definição.

3. Relação de equivalência sse:
aRa (reflexividade). Se u = v, então o caminho vazio (nenhum vértice ou aresta) é um caminho válido de u a v.
Se aRb então bRa (simetria). Como o grafo é não orientado, então se S é a sequência que forma o caminho de u até v, então a sequência invertida de S forma um caminho de v até u (pois se uma aresta liga 'a' a 'b', ela liga 'b' a 'a').
Se aRb e bRc, então aRc (transitividade). Seja S1 a sequência que forma o caminho de u até v. Seja S2 a sequência que forma o caminho de v até um vértice x. Então, ao tomarmos S3 como o caminho de u até v expresso em S1, concatenado do caminho de v até x expresso por S2 (evidentemente, como o último elemento de S1 é o mesmo de S2, ele só aparecerá uma vez no ponto de concatenação), S3 é um caminho de u até x (uRx).

4. Grafo simples: grafo que não possui laços nem arestas múltiplas. Sabemos que |E| = C(|V|, 2) em Kv, pois existe uma aresta entre quaisquer dois vértices do grafo. O número de arestas é, portanto, a combinação do número de vértices, 2 a 2. Suponhamos que exista um grafo simples, não completo, tal que |E| = C(|V|, 2). Ora, como o grafo completo abrange todas as possíveis arestas num grafo simples com |V| vértices (pela sua definição), então G deve conter um subconjunto de arestas do grafo completo. Porém, |E| é igual ao número de arestas de Kv, pela hipótese. Logo, E = conjunto de arestas de Kv (mais uma vez, porque Kv contém o conjunto maximal de arestas para um grafo simples com |V| vértices). Um absurdo, pois assumimos que G != Kv. Portanto, se |E| = C(|V|, 2), então G = Kv.