\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}{Cuarta tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. La tarea se entrega individualmente.
\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 más simples.

\begin{enumerate}

\item Prueba que toda gráfica posee una trayectoria de longitud al menos $\delta(G)$. (\emph{Sugerencia.} Considera una trayectoria de longitud máxima, ¿en dónde viven los vecinos de los extremos de la trayectoria?).
\item Dada $G$ una gráfica conexa de orden once y $e$ una arista de corte (también llamadas \emph{puentes}) de $G$ y $v$ un vértice de $G$.
\begin{enumerate}
\item  Muestra que existe una componente de $G-e$ que posee al menos seis vértices.
\item  Muestra que $G-v$ no siempre tiene una componente con al menos seis vértices.
\end{enumerate}
\item Prueba que si $e$ es un puente en $G$ entonces existen dos vértices $u$ y $v$ tales que toda $(u$, $v)$-trayectoria pasa por $e$.
\item Prueba que si $G$ es un bosque con $\omega$ componentes conexas entonces $m=n-\omega$.
\item Prueba que la distancia entre vértices en una gráfica es una métrica, es decir, que:
\begin{enumerate}
 \item $d(v$, $u)\geq 0$ y $d(v$, $u)=0$ si y sólo si $v=u$.
 \item $d(v$, $u)=d(u$, $v)$.
 \item $d(v$, $u) \leq d(u$, $w)+d(w$, $u)$.
\end{enumerate}
\item Prueba que toda componente conexa de un bosque es un árbol.
\item Prueba que todo bosque es bipartito.
\end{enumerate}

\section*{Extras}
 \begin{enumerate}[A.]
\item Muestra que un árbol con exactamente dos hojas es una trayectoria.
\item Prueba que una gráfica $G$ es un bosque si y sólo si toda subgráfica inducida de $G$ contiene un vértice de grado a lo más 1.
\item Una hidrocarburo saturado es una molécula $C_mH_n$ en la cual todo átomo de carbono tiene cuatro enlaces, todo átomo de hidrógeno tiene un solo enlace y ninguna sucesión de enlaces forman un ciclo. Muestra que, para todo entero positivo $m$, $C_mH_n$ puede existir si y sólo si $n=2m+2$.
\end{enumerate}


\end{document}