Seminario de análisis combinatorio

Tercera tarea

Se entrega el martes 4 de diciembre entre 11 y 12 en el Aula 3 de Becarios

1. Sea D una digráfica infinita. Demuestra que todo seminúcleo está contenido en un seminúcleo maximal.

2. Sean D una digráfica y h un entero mayor o igual que dos. Si H una subdigráfica de D tal que todo ciclo de longitud no congruente con cero módulo h tiene al menos dos flechas en F (D) \ F (H) entonces para cada componente fuertemente conexa B de H, la digráfica D[V (B)] es cíclicamente h-partita.

3. Sean D una digráfica. Si H es una subdigráfica de D tal que todod ciclo de longitud impar tiene al menos dos flechas en F (D) \ F (H) entonces para cada componente fuertemente conexa C de H, la digráfica D[V (C] es bipartita.

4. (Punto extra.) Sea D una digráfica. D es bipartita si y sólo si existe una subdigráfica fuertemente conexa H de D tal que cada ciclo de longitud impar tiene al menos dos flechas en F (D) \ F (H).