Lista de Exercícios 3

Prévia do material em texto

III Lista de Exerc´ıcios de Ana´lise Combinato´ria.
Profo Danilo Artigas
Po´lo Universita´rio de Rio das Ostras
UFF
1. Exerc´ıcios 2.1 a 2.8; 2.16; 2.18; 2.32 e 2.33.
2. Prove que δ ≤ 2m
n
≤ ∆.
3. Prove que, em um grafo qualquer, o nu´mero de ve´rtices de grau ı´mpar e´
par.
4. Determine condic¸o˜es sobre n para estabelecer se Kn e´ euleriano.
5. Determine condic¸o˜es sobre n para estabelecer se Kn e´ hamiltoniano.
6. O complemento de um grafo bipartido e´ bipartido? Prove ou de contra-
exemplo.
7. O complemento de um grafo hamiltoniano e´ hamiltoniano? Prove ou de
contra-exemplo.
8. Desenhe todos os grafos isomorfos de 4 ve´rtices; e todos os grafos isomorfos
de 5 ve´rtices.
9. Seja G = (V,E) um grafo. Prove que e(v) ≥ diam(G)2 , para todo v ∈ V .
10. Prove que numa festa com 6 pessoas existem 3 que se conhecem mutu-
amente ou na˜o se conhecem mutuamente. Onde conhecer e´ uma relac¸a˜o
sime´trica, i.e., se Joa˜o conhece Maria, enta˜o Maria conhece Joa˜o.
1