\documentclass[letterpaper, 12pt]{article}
% \usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{latexsym} 
\usepackage{amssymb}  
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath} 
\usepackage{graphics}
\usepackage{color}
\usepackage[all]{xy}
\usepackage{xcolor} 
\usepackage{wrapfig} 
\usepackage{pdfsync}
\usepackage{floatflt}
\usepackage{paralist}
% \usepackage{makeidx}
\usepackage{ifpdf}
% \usepackage{graphfig}
% \usepackage{subfig}
\usepackage{graphicx} 
\usepackage{mathrsfs}
\usepackage{caption} 
\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\usepackage{pgf,tikz}
\usetikzlibrary{arrows}

\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{\mcd}{mcd}

\begin{document}
\header{Gráficas y juegos}{Tercera tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. La tarea se puede entregar en equipos de dos personas.
\paragraph{ }
Recuerden que las definiciones son las importantes. Para probar algo no siempre es bueno sobreargumentar (ni tampoco quedar falto de argumentos). Los mejores argumentos suelen ser los simples.

\begin{enumerate}

\item 
\begin{enumerate}
\item Muestra que si $G$ es bipartita y $H$ es una gráfica isomorfa a $G$, entonces $H$ es bipartita.
\item Muestra que si $G$ es conexa y $H$ es una gráfica isomorfa a $G$, entonces $H$ es conexa.
\end{enumerate}

\item Muestra que $G$ es conexa si y sólo si existe un camino abierto que pasa por todos los vértices de $G$.
\item Considera $G$ una gráfica de orden trece con tres componentes conexas. Prueba que $G$ posee una componente de orden al menos cinco.
\item Demuestra que una gráfica $G$ es bipartita si y sólo si todas sus componentes conexas son bipartitas.
\item Prueba que toda gráfica $G$ contiene una trayectoria de longitud al menos $\delta(G)$.
\item Demuestra que si $\delta(G)\geq 2$ entonces $G$ contiene un ciclo.
\end{enumerate}

\section*{Extras}
 \begin{enumerate}[A.]
\item  Sea $G$ una gráfica de orden $n$ par tal que al menos dos de las componentes de $G$ son completas, prueba que el máximo tamaño posible de $G$ es $\frac{n^{2}-2n}{4}$.
\item Sea $A$ la matriz de adyacencia de una gráfica $G$ con conjunto de vértices $V(G)=\{v_{1}$, $v_{2}$, \dots, $v_{n}\}$, prueba que la entrada $a_{ij}$ de la matriz $A^{k}$, es el número total de $(v_{i}$, $v_{j})$-caminos en $G$ de longitud $k$.
\item Prueba que dos gráficas $G$ y $H$ son isomorfas si y sólo si existe un arreglo de sus vértices para el cual sus matrices de adyacencia son idénticas.

\end{enumerate}


\end{document}