4 Lista de Matemática Discreta 2021 2

4a lista de Matematica Discreta 20212 1 Encontre todos os grafos com 2 3 ou 4 vertices 2 Sejam G V A um grafo e u v V tais que u v Mostre que existe um passeio ligando u e v se e somente se existe um caminho ligando u e v O que podemos dizer sobre a definicao de conexidade 3 Mostre que todo grafo com mais de um vertice tem dois vertices com o mesmo grau 4 Mostre que um grafo com n vertices e C2 n1 arestas e sempre conexo 5 Todo grafo hamiltoniano tambem e euleriano E o contrario 6 a Mostre com um exemplo que e possıvel remover apenas uma aresta de um grafo conexo qualquer G de forma que o grafo resultante deixa de ser conexo b Mostre que se a aresta removida for de um ciclo entao o grafo resultante e conexo 7 E possıvel obter um grafo planar removendo uma aresta de K5 1