Universidad Nacional de IngenierıaFacultad de CienciasEscuela Profesional de Matematica Ciclo 2012-2

Sexta Practica Calificada de Introduccion a la Matematica DiscretaCM-254 A

1. Pruebe que un grafo de n vertices con c componentes tiene al menos n− c aristas.

2. Sea G un grafo 2-conexo tal que G?e, con e ∈ E(G) no es 2-conexo, demuestre que por lomenos un vertice de G tiene grado 2.

3. Si un arbol m-ario de altura h tiene l hojas, pruebe que h > logm(l).

4. Pruebe que si T es un arbol de orden n con un vertice de grado k entonces posee, al menos,k vertices de grado uno.

Observaciones:

Resuelva usando solo la teorıa desarrollada en clase.

Argumente cada paso realizado en el desarrollo de cada solucion.

No se consideraran reclamos de preguntas resueltas desordenadamente y/o sin claridad.

Uni, 03 de diciembre de 2012

E. Kenny Venegas P/Jonathan Munguıa.