\documentclass[letterpaper, 12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{palatino}
\usepackage{latexsym,amssymb,amsfonts,amsmath}
\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{paralist}
\usepackage{graphics}
\usepackage[all]{xy}
\pagestyle{empty}
 
\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\theoremstyle{plain}
\newtheorem{proposicion}{Proposition}
\newtheorem{lema}{Lema}
\newtheorem{teorema}{Teorema}
\newtheorem{corolario}{Corolario}
\newtheorem{conjetura}{Conjetura}

\theoremstyle{definition}
\newtheorem{definicion}[proposicion]{Definición}

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\cp}{cp}
\DeclareMathOperator{\cut}{c}
\DeclareMathOperator{\p}{p}


\begin{document}
\header{Teoría de las Gráficas}{Undécima tarea\\2 de diciembre de 2009}


\begin{enumerate}[1.]
 \item Para cada una de las gráficas 1(a)-1(e) encuentra una coloración minimal propia.
 \item Cada una de las gráficas 2(a)-2(e) tiene número cromático menor o igual que cuatro.  Argumenta por qué teorema de coloración puedes deducir éso y encuentra una coloración minimal propia.
 \item Supón que $H$ es una subgráfica de $G$.  ¿Necesariamente pasa que $\chi(H)\leq\chi(G)$?
 \item Supón que una gráfica $G$ es la unión de dos subgráficas $G_1$ y $G_2$ que tienen un único vértice en común.  Muestra que el número cromático de $G$ es el máximo de los números cromáticos de $G_1$ y $G_2$.
 \item Muestra que en cualquier coloración minimal propia, para cualesquiera dos colores existen vértices adyacentes con esos colores.
\end{enumerate}

\subsubsection*{Extras}
\begin{enumerate}[A.]
\item Prueba que si cualesquiera dos ciclos de longitud impar tienen un vértice en común
en $G$ entonces $G$ puede colorearse con a lo más cinco colores.
\item Si $G$ es una gráfica con exactamente un ciclo de longitud impar entonces $\chi(G) = 3$.
\item Si $x$ es un vértice de $G$ de grado menor que $n$ (un número entero positivo), muestra que $G$ es $n$-coloreable si y sólo si $G - x$ lo es.
\end{enumerate}

\end{document}