Lista de Exercícios 4

Prévia do material em texto

IV Lista de Exerc´ıcios de Ana´lise Combinato´ria.
Profo Danilo Artigas
Po´lo Universita´rio de Rio das Ostras
UFF
1. Prove que toda a´rvore possui pelo menos 2 folhas.
2. Prove que toda a´rvore e´ um grafo bipartido. E descreva um mecanismo
para determinar uma bipartic¸a˜o de uma a´rvore.
3. Seja G = (V,E) uma floresta. Prove que |E| = |V | − ω(G), onde ω(G) e´
o nu´mero de componentes conexas de G.
4. Prove que T = (V,E) e´ uma a´rvore se, e somente se, T e´ conexo e |E| e´
mı´nimo.
5. Uma a´rvore enraizada T = (V,E) e´ denominada estritamente bina´ria se
todo ve´rtice de T possui zero ou dois filhos. Seja f o nu´mero de folhas de
T . Prove que se T e´ uma a´rvore estritamente bina´ria onde |V | > 2, enta˜o
|V | = 2f − 1.
6. Desenhe todas as a´rvores na˜o isomorfas com 5 e 6 ve´rtices.
1