\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}{Quinta 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.

\begin{enumerate}
\item Prueba que los siguientes enunciados son equivalentes:
\begin{compactenum}
 \item $e$ es un puente de $G$.
 \item Existen dos vértices en $G$, $u$ y $w$, tales que toda $(u$, $w)$-trayectoria pasa por $e$.
 \item Existe una partición de los vértices de $G$ en dos conjuntos, $V_1$ y $V_2$, tal que toda $(V_1$, $V_2)$-trayectoria pasar por $e$. Define explícitamente qué es una $(V_1$, $V_2)$-trayectoria.
\end{compactenum}

 \item Da un ejemplo para mostrar que si $P$ es una $(u$, $v)$-trayectoria en una gráfica no separable distinta de $K_2$ no necesariamente existe una $(u$, $v)$-trayectoria $Q$ internamente ajena a $P$.

 \item Considera $G$ una gráfica con al menos tres vértices. Prueba que son equivalente:
 \begin{compactenum}
  \item $G$ es un bloque.
  \item Dados dos vértices y una arista existe una trayectoria entre los vértices que pasa por la arista.
  \item Dados tres vértices existe una trayectoria entre cualquier par de ellos que pasa por el tecero.
  \item Dados tres vértices existe una trayectoria entre cualquier par de ellos que no pasa por el tercero.
 \end{compactenum}

 \item Considera $T$ un árbol arbitrario con $k+1$ vértices. Muestra que si $G$ tiene grado mínimo al menos $k$ entonces $G$ posee una subgráfica isomorfa a $T$.
 
 \item Muestra que el número de bloques en una gráfica es igual a
 \begin{displaymath}
  \omega + \sum_{v \in V(G)} (b(v)-1)\text{,}
 \end{displaymath}
 donde $b(v)$ denota el número de bloques en los que está $v$.
 
\end{enumerate}

\section*{Extras}
\begin{enumerate}[A.]
 \item Recuerda que un bloque es una subgráfica maximal sin vértices de corte. Prueba que si $G$ es una gráfica sin ciclos pares (\textit{i.e.}, de longitud par) entonces cada bloque de $G$ es $K_1$, $K_2$ o un ciclo de longitud impar. (\emph{Sugerencia.} Fíjate en las componentes conexas y considera dos casos: no posee ciclos o posee al menos un ciclo. En el último caso, prueba que no puede tener más aristas ni vértices usando el teorema de caracterización de bloques).

\item Considera $G$ una gráfica no separable con al menos dos vértices. Toma un vértice $v$ que no esté en $G$ y $u$, $w \in V(G)$. Define $G'$ como la gráfica cuyo conjunto de vértices es $V(G) \cup \{ v \}$ y cuyo conjunto de aristas es $A(G) \cup \{vu$, $vw\}$. Prueba que $G'$ es no separable.

\item Considera $G$ una gráfica no separable con al menos tres vértices y $X$ y $Y$ dos subconjuntos ajenos de vértices de $G$ con al menos dos vértices cada uno. Muestra que $G$ posee dos trayectorias ajenas (no internamente ajenas) $P$ y $Q$ tales que:
\begin{compactenum}
 \item $P$ y $Q$ empiezan en $X$,
 \item $P$ y $Q$ terminan en $Y$ y
 \item ningún vértice interno de $P$ y $Q$ pertenece a $X \cup Y$.
\end{compactenum}
(\emph{Sugerencia.} Usa el inciso anterior y el teorema de caracterización de bloques).


\end{enumerate}


\end{document}