Lista11-MO405

Prévia do material em texto

Lista de Exercícios 11
Resolução:
Resolução:
3-cubo é planar:
4-cubo é não planar:
Resolução:
Junto com b.
Resolução:
Resolução:
Resolução:
Falso. Exemplo: K5.
n = 5; m = 10
10 3*5 - 6 = 9 (OK, mas K5 não é planar)
Resolução:
Resolução:
Conferir. Um k3,3 possui n=6 e m=9 pela definição. Além disso, o menor ciclo possível tem tamanho 4 (basta percorrer um caminho p4 e depois voltar ao vértice inicial). Usando o resultado acima, temos que o limite superior do número de arestas é m <= 2n-4 = 2*6 - 4 = 12 - 4 = 8. Portanto, Um k3,3 não é planar pois possui um vértice a mais do que o permitido pela equação.
Conferir.
Um P4 tem uma única face composta de 3 arestas de corte.
Portanto, d(P4) = 3 (arestas) * 2 (peso de aresta de corte) = 6.
Resolução (Semelhante ao exercício 8a, mas agora d(f) >= g):
Solução:
Dado que é possível colorir um grafo planar com 4 cores (X(G) (G)), a desigualdade é válida.
Temos que X(G) >= n/alfa
alfa >= n/X(G) = n/4
Resolução: