Exemplos de Fixação

1. Desenhe um grafo com 5 vértices (v1, v2, v3, v4, v5), em que grau(v1) = 3, v2 é um vértice ímpar, grau(v3) = 2, e v4 e v5 são adjacentes.
2. Provar que o número de vértices de grau ímpar é par.
3. É possível ter um grafo com seqüência de graus 5, 4, 4, 3, 2, 1.
4. Nos encontros sociais, a forma mais tradicional de cumprimento é o aperto de mão. Provar que o total de apertos de mão em qualquer ocasião deve ser par. Prove também que o número de pessoas que cumprimenta um número ímpar de pessoas é par.
5. Como tornar os grafos G1 e G2 isomórficos?
6. A propriedade de isomorfismo de grafos é simétrica? Reflexiva? Transitiva?
7. Se G1 e G2 são isomórficos, qual a relação entre número de vértices de G1 e G2? E sobre o número de arestas? E a seqüência de graus?
8. Os grafos G1 e G2 são isomórficos? E G3 e G4?
9. O que são grafos bipartidos? Mostre exemplos?
10. Subgrafos de um grafo bipartido é bipartido?
11. Qual o número de arestas de um grafo completo com 6 vértices?
12. Determine o complemento do Grafo G1.
13. Clique e Conjunto independente de vértices.