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

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. La tarea se entrega 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.
\paragraph{ }

Recuerda que dada una gráfica $G$ y dados $v$ un vértice en $G$ y $e$ una arista de $G$, $G-v$ es la gráfica cuyo conjunto de vértices es $V(G) \setminus \{v\}$ y cuyo conjunto de aristas es $A(G) \setminus \{ xv : xv \in A(G)\}$ y $G-e$ es la gráfica cuyo conjunto de vértices coincide con el de $G$ pero su conjunto de aristas está dado por $A(G) \setminus \{e \}$. Observa que tanto en $G-v$ como en $G-e$, ``$-$'' denota una nueva operación.

Una arista se dice \emph{cíclica} si pertenece a al menos un ciclo de la gráfica. Una arista se dice \emph{acíclica} si no pertenece a ningún ciclo de la gráfica.

Dada $G$ una gráfica conexa, sabemos que $m \geq n-1$.
\begin{enumerate}
 \item Prueba que una arista $e$ en una gráfica conexa $G$ es cíclica si y sólo si $G-e$ es conexa. O bien, prueba la equivalencia: una arista $e$ en una gráfica conexa $G$ es acíclica si y sólo si $G-e$ es disconexa.

 \item Prueba que si $\delta(G)\geq 2$ entonces $G$ posee un ciclo. (\emph{Sugerencia.} Considera una trayectoria de longitud máxima en $G$, ¿qué pasa con los vértices de los extremos?)

 \item \begin{compactenum} \item Considera $G$ una gráfica conexa con un vértice de grado uno, llamémosle $v$. Prueba que $G-v$ es conexa.
        \item Considera $G$ una gráfica conexa, $u$ un vértice de $G$ y $v$ un vértice que no esté en $G$. Prueba que la gráfica con conjunto de vértices $V(G) \cup \{ v \}$ y conjunto de aristas $A(G) \cup \{ uv \}$ \textbf{es conexa}.
       \end{compactenum}

 \item Prueba que si $G$ es conexa y no posee ciclos entonces $m = n-1$. Concluye que si $G$ no posee ciclos entonces $m \leq n-1$. De aquí que si $m \geq n$ entonces $G$ posee al menos un ciclo. (\emph{Sugerencia.} Hazlo por inducción y utiliza los dos ejercicios anteriores.)

 \item Prueba que si $G$ es conexa y satisface que $m=n-1$ entonces $G$ no posee ciclos (\emph{Sugerencia.} \textbf{Utiliza el primer problema}).

 \item Prueba que si $G$ no posee ciclos y satisface que $m=n-1$ entonces $G$ es conexa. (\emph{Sugerencia.} Hazlo por inducción).
\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 Demuestra que una gráfica $G$ es bipartita si y sólo si todas sus componentes conexas son bipartitas.


\end{enumerate}


\section*{Extras}
 \begin{enumerate}[A.]
 \item Dada $G$ una gráfica sin vértices aislados, prueba que si $G$ no posee ciclos de longitud impar entonces $G$ es bipartita.

\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$.


\end{enumerate}


\end{document}