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

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

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas\hyphenation{res-pues-tas}. La tarea se puede entregar en equipos de dos personas (si el equipo no coincide con el de la tarea anterior).
\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 Dada una gráfica $G$, $\cp(G)$ es el número de vértices de corte de la gráfica $G$. Prueba que:
\begin{enumerate}
\item Si $e$ es una arista cíclica de $G$ entonces $\cp(G)\leq \cp(G-e)$. (\emph{Sugerencia.}\hyphenation{Su-ge-ren-cia} Prueba que todo vértice de corte de $G$ es vértice de corte en $G-e$.
\item Si $T$ es un árbol generador de $G$, prueba que $\cp(G) \leq \cp(T)$.
\item Deduce que toda gráfica posee al menos dos vértices que no son de corte.
\end{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$.
\end{compactenum}

\item Da un ejemplo para mostrar que si $P$ es una $(u$, $v)$-trayectoria en una gráfica no separable con al menos tres vértices entonces no necesariamente existe una $(u$, $v)$-trayectoria $Q$ internamente ajena a $P$.

\item Prueba que si $G$ tiene un puente, entonces tiene un vértice de corte y muestra que el recíproco no necesariamente se cumple.

\item Demuestra que si $v$ es un vértice de corte en $G$, entonces $v$ no es de corte en el complemento de G.
\end{enumerate}

\section*{Extras}
\begin{enumerate}[A.]
\item Una arista $uv$ es la diagonal de un ciclo $\gamma$ en $G$ si $\{u,v\}\subset V(\gamma)$ y $uv\notin E(\gamma)$. Prueba que una arista $e$ de una gráfica no separable con al menos tres vértices es diagonal de un ciclo en $G$ si y sólo si $G-e$ es no separable con al menos tres vértices.
 \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$ (\emph{Sugerencia}. Usa inducción sobre el número de vértices de $T$).

\item Prueba que no existe una gráfica $3$-conexa de tamaño $7$ (\emph{Sugerencia}. Considera un conjunto de corte mínimo en $G$. Al quitarlo ¿qué te queda?)
\end{enumerate}


\end{document}