\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}
\DeclareMathOperator{\linea}{L}

\begin{document}
\header{Gráficas y juegos}{Quinta 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.

\begin{enumerate}
\item Demuestra que toda gráfica conexa posee un árbol generador.

\item Denotamos por $\cp(G)$ al número de vértices de corte de una gráfica dada $G$. Prueba que:
\begin{enumerate}
\item Si $e$ es una arista cíclica de $G$ entonces $\cp(G)\leq \cp(G-e)$. (\emph{Su\-gerencia.} Prueba que todo vértice de corte de $G$ es vértice de corte en $G-e$).

\item Supón que $G$ es conexa, prueba que si $T$ es un árbol generador de $G$, entonces $\cp(G)\leq \cp(T)$. 

\item Deduce que toda gráfica posee al menos dos vértices que no son de corte. 

\item ¿Cuál es el número máximo de vértices de corte que puede tener una gráfica de orden $n$?
\end{enumerate}

\item Demuestra que si $v$ es un vértice de corte en $G$ entonces $v$ no es de corte en $\overline{G}$ (el complemento de $G$). 

\item Prueba que si $G$ es conexa y de orden al menos tres, las siguientes afirmaciones son equivalentes:

\begin{enumerate}
\item $G$ no posee vértices de corte.
\item Para cualquier par de vértices $u$ y $v$, existe un ciclo de $G$ que los contiene.
\item Para cualquier vértice $u$ y cualquier arista $e$, existe un ciclo de $G$ que los contiene.
\end{enumerate}

La primera implicación se vio en clase. La segunda implicación se hace muy parecido a la prueba de la primera implicación.

\item Prueba que la gráfica de bloques y de vértices de corte de una gráfica conexa es un árbol.


\item Sea $G$ una gráfica conexa y $b(v)$ el número de bloques que contienen al vértice $v$. Prueba que el número de bloques de $G$ es $$1+\sum_{v\in V}(b(v)-1)$$.
\end{enumerate}

\textsc{Extras}
\begin{enumerate}

\item Prueba que el número de hojas de un árbol no trivial $T$ con $V(T)=\{v_{1},v_{2},\dots, v_{n}\}$ es: $$2+\sum_{d(v_{i})\geq 3}(d(v_{i})-2)$$.

\item Dada $G$ una gráfica, definimos la \emph{gráfica de líneas} de $G$, $\linea(G)$, como la gráfica cuyos vértices son las aristas de $G$ y dos vértices en $\linea(G)$ son adyacentes si las aristas correspondientes en $G$ son adyacentes. ¿Es cierto que si $e$ es una arista de corte en $G$ entonces $e$ es un vértice de corte en $\linea(G)$? (Justifica tu respuesta).

\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 ismorfa a $T$. (\emph{Sugerencia.} Usa inducción sobre el número de vértices de $T$)
\end{enumerate}


\end{document}