Examen parcial: Matemática discreta

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

Sea G una gráfica simple sin ciclos. Demuestra que $|E| = |G|-\omega(G)$ .
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.
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$ .
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?
Sea G una gráfica con 10 vértices y 38 aristas. Demuestra que contiene a $K_4$ como subgráfica inducida.
¿Cuantos automorfismos tiene la gráfica siguiente?