Practica de matematica discreta

PROBLEMARIO 1
Ejercicio 1. Sea G un grafo simple, con al menos dos v´rtices. Probar que G posee e dos v´rtices del mismo grado. e Ejercicio 2. Dibuje todos los grafos regulares de 6 v´rtices. e Ejercicio 3. ¿Existe un grafo 3-regular y de 9 v´rtices? e Ejercicio 4. Sea G un grafo con p v´rtices. Pruebe que si la valencia m´ e ınima es mayor o igual a
p−1 , 2

entonces G es conexo.Ejercicio 5. Sea G un grafo con 6 v´rtices v1 , . . . , v6 tal que: val(v1 ) = val(v2 ) = 1, e val(v3 ) = val(v4 ) = 2, val(v5 ) = val(v6 ) = 3. ¿Puede ser G un ´rbol? a Ejercicio 6. ¿Cu´les arboles son bipartitos? a ´ Ejercicio 7. Pruebe que si en un grafo G se cumple que dos v´rtices est´n unidos por e a un unico camino, G es un arbol. ´ ´ Ejercicio 8. Puebe que no existe un grafo con v´rtices de grado1,3,3,3. e Ejercicio 9. ¿Existe un grafo con v´rtices de grado 2,3,3,4,4,5? e Ejercicio 10. Sea G un grafo con p v´rtices y q aristas tal que q ≥ p ≥ 3. Deducir que e G tiene un ciclo. Ejercicio 11. Sea G1 = C6 y G2 = K2 . Calcular G1 × G2 . Ejercicio 12. Sea φ : G → H un isomorfismo de grafos. Pruebe que si v1 , v2 , v3 es un tri´ngulo en G, entonces φ(v1 ), φ(v2 ), φ(v3 ) es un tri´ngulo en H. aa Ejercicio 13. Un grafo se dice autocomplementario si es isomorfo con su complemento. Pruebe que el unico ciclo autocomplementario es C5 . ´ 1

Ejercicio 14. Pruebe o refute si los siguientes grafos son isomorfos.

Ejercicio 15. Pruebe o refute si los siguientes grafos son isomorfos.

Ejercicio 16. Pruebe o refute si los siguientes grafos son isomorfos.

Ejercicio 17. Pruebe o refute silos siguientes grafos son isomorfos.

Ejercicio 18. Pruebe o refute si los siguientes grafos son isomorfos.

2

Ejercicio 19. Pruebe o refute si los siguientes grafos son isomorfos.

Ejercicio 20. Probar que salvo isomorfismo, existen exactamente 11 grafos de 4 v´rtices. e ¯ = Ejercicio 21. Probar que Cn ∼ Cn ⇔ n = 5. Ejercicio 22. Calcule todos los automorfismos de los siguientes grafos:Ejercicio 23. ¿Cu´ntos automorfismos tienen los grafos: a a) K3,4 b) K3,3,3 ?

Ejercicio 24. Elena y Dora invitan a 10 amigas acenar. En este grupo de 12 todos conocen al menos 6 personas. Prueben que se pueden sentar los 12 alrededor de una mesa circular de modo que todas las personas conozcan a los que est´n sentados a su a lado. Ejercicio 25. Sea G1 ≈ G2 . Pruebe que si uno de ellos esconexo, el otro tambien lo es. Ejercicio 26. ¿Es el producto cartesiano de grafos Eulerianos Euleriano? 3

Ejercicio 27. Calcular el n´mero de aristas del grafo: K2,2,...,2 . ¿Es Euleriano? u Ejercicio 28. Deducir que los grafos:

son planares. Ejercicio 29. Probar que K3,3 no es planar. Ejercicio 30. ¿Es el grafo:

planar?
n Ejercicio 31. ¿Para que valores de n es Qn planar? Y Qn = K2 .Ejercicio 32. ¿Es el grafo:

planar? Ejercicio 33. Encontrar un grafo no planar que sea homeom´rfico a K5 o K3,3 . ¿Cono tradice esto el teorema de Kuratowski? 4

Ejercicio 34. Encontrar un grafo no planar que no sea contraible a K5 o K3,3 . Ejercicio 35. ¿Es un grafo bipartito hamiltoniano? Ejercicio 36. ¿Es el grafo:

hamiltoniano? Ejercicio 37. Sea G un grafo regular de orden par ≥ 4. Pruebeque G o su complemento es hamiltoniano. Ejercicio 38. ¿Es el grafo:

hamiltoniano? Ejercicio 39. ¿Es el grafo:

5

hamiltoniano? Ejercicio 40. ¿Es el grafo:

hamiltoniano? Ejercicio 41. Sea el grafo: K(n,n,n+1) . ¿Es Euleriano? ¿Es hamiltoniano? Ejercicio 42. ¿Es el grafo:

hamiltoniano? Encontrar un ciclo hamiltoniano. Ejercicio 43. Sea G un grafo con 31 v´rtices y 437 aristas. ¿Es GHamiltoniano?. e Justifique. Ejercicio 44. Enuncie el teorema de Chvatal y dibuje un grafo que ponga en evidencia que el rec´ ıproco es falso. 6

n Ejercicio 45. Probar que K2 es hamiltoniano, para n ≥ 2.

Ejercicio 46. ¿Es el grafo:

hamiltoniano? Ejercicio 47. Probar que el producto cartesiano de grafos hamiltoniano es hamiltoniano. Ejercicio 48. ¿Es el grafo:

hamiltoniano? Pruebe o...