Examen parcial: Matemática discreta

Este es el 3er parcial del curso de matemática discreta (tema: teoría de gráficas).

  1. Sea G una gráfica simple sin ciclos. Demuestra que |E| = |G|-\omega(G).
  2. Sea G una gráfica simple (posiblemente disconexa). Si G es 4-regular, entonces puedes colorear las aristas de rojo o azul de forma que cada vértice tenga el mismo número de aristas de cada color.
  3. Si en una gráfica simple cada vértice tiene grado k (k\ge 2), prueba que debe existir un ciclo de longitud mayor o igual a k+1.
  4. Si G, H son dos gráficas simples con el mismo número de vértices y las listas ordenadas de los grados de los vértices en cada gráfica son iguales, ¿necesariamente son gráficas isomorfas?
  5. Sea G una gráfica con 10 vértices y 38 aristas. Demuestra que contiene a K_4 como subgráfica inducida.
  6. ¿Cuantos automorfismos tiene la gráfica siguiente?
Anuncios

Un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s