Lista-6

Prévia do material em texto

Lista 6 de Matemática Combinatória (Grafos)
1 Desenhe todas as árvores não isomorfas com 7 vértices.
2 Prove que as seguintes afirmações são equivalentes:
(i) G é uma árvore;
(ii) G é aćıclico e a adição de qualquer aresta produz um grafo com exatamente um ciclo.
3 Mostre que toda árvore possui pelo menos ∆ (o grau máximo em um grafo) folhas.
4 Mostre que uma árvore com pelo menos dois vértices e com exatamente dois vértices de grau um é um
caminho.
5 Mostre que toda árvore é um grafo bipartido..
6 Um grafo aćıclico é dito uma floresta. Prove que cada componente conexa de uma floresta é uma árvore.
Prove também que um grafo é uma floresta se e somente se o seu número de arestas é igual ao seu número
de vértices menos o seu número de componentes conexas.
7 Mostre que um grafo conexo T é uma árvore se e somente se cada aresta de T for uma ponte.
8 Prove que se uma aresta de um grafo G estiver presente em toda árvore geradora de G, então esta aresta é
uma ponte de G.
9 Prove ou dê contra-exemplo.
(i) Se v é uma articulação de G, então v é articulação de todo subgrafo induzido que o contém.
(ii) Se G contém uma ponte, então G contém uma articulação.
(iii) Se G contém uma articulação, então G contém uma ponte.
10 Dê um exemplo com no máximo 6 vértices para cada ı́tem a seguir:
(i) Um grafo hamiltoniano que não seja euleriano.
(ii) Um grafo euleriano que não seja hamiltoniano.
11 Mostre que um grafo bipartido com um número ı́mpar de vértices não pode ser hamiltoniano.