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

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

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

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\mcd}{mcd}

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

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. 
\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.
\paragraph{}
Pueden entregar la tarea en grupos de dos personas si en la siguiente tarea trabajan en un grupo distinto.

\begin{enumerate}
\item La siguiente figura muestra el plano de una casa; ¿es posible que una persona pase por cada una de las puertas de la casa una sola vez? Modela este problema con una gráfica y, en caso de que sea posible recorrer la casa de este modo, muestra cómo puede hacerse, en caso contrario explica por qué no.
\begin{figure}[h]
	\centering
		\includegraphics{plano.pdf}
	\label{fig:plano}
\end{figure}


\item Prueba que una gráfica es euleriana si y sólo si existe una partición de sus aristas en ciclos.

\item Muestra que la gráfica abajo no es hamiltoniana.
\begin{figure}[h]
	\centering
		\includegraphics{H.pdf}
	\label{fig:H}
\end{figure}

\item Prueba que si $G$ es una gráfica hamiltoniana entonces para subconjunto $S$ de los vértices de $G$ se tiene que:
\begin{displaymath}
 \omega(G-S) \leq \lvert S \rvert\text{.}
\end{displaymath}


% \item Investigue cuál es la gráfica asociada a la figura geométrica llamada \textit{icosaedro} y muestre que dicha gráfica es hamiltoniana.

\item \begin{enumerate}
 \item Prueba que si $G$ es una gráfica con al menos tres vértices y \emph{para cada par de vértices no adyacentes} $u$ y $v$ se tiene que:
\begin{displaymath}
 d(u)+d(v)\geq n
\end{displaymath}
entonces $G$ es hamiltoniana si y sólo si $G+uv$ es hamiltoniana.
 \item Deduce que si una gráfica con al menos tres vértices satisface que para cada par de vértices no adyacentes $u$ y $v$ se tiene que $d(u)+d(v)\geq n$ entonces $G$ es hamiltoniana.
\end{enumerate}

\item Prueba o da un contraejemplo de las siguientes afirmaciones:
\begin{enumerate}
\item Toda gráfica euleriana es hamiltoniana.
\item Toda gráfica hamiltoniana es euleriana.
\end{enumerate}

\end{enumerate}

\end{document}