\documentclass[letterpaper, 12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{palatino}
\usepackage{latexsym,amssymb,amsfonts,amsmath}
\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{paralist}
\usepackage{graphics}
\usepackage[all]{xy}
\pagestyle{empty}
 
\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\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{\cut}{c}
\DeclareMathOperator{\p}{p}


\begin{document}
\header{Teoría de las Gráficas}{Sexta tarea\\8 de octubre de 2009}

\begin{enumerate}[1.]
\item Considera $T$ un árbol de orden quince tal que $1 \leq d(v) \leq 4$ para cada vértice $v$ en $T$.  Supón que $T$ contiene exactamente nueve hojas y exactamente tres vértices de grado cuatro.  ¿Cuántos vértices de grado tres tiene $T$?  Justifica tu respuesta y dibuja un árbol que satisfaga lo anterior.

\item Los grados de los vértices de un árbol $T$ de orden dieciocho son uno, dos y cinco.  Si $T$ posee exactamente cuatro vértices de grados dos, ¿cuántas hojas tiene $G$?

\item Considera $T$ un árbol y $n_i$ el número de vértices de grado $i$ en $T$.  ¿Cuáles de las siguientes afirmaciones son verdadera?
\begin{compactitem}
\item Si $T$ no es una trayectoria entonces $n_1 \geq n_2$.
\item Si $n_2=0$ entonces $T$ tiene más hojas que otros vértices.
\end{compactitem}

\item Considera $T$ un árbol de orden $n$.  Muestra que los vértices de $T$ siempre pueden ser nombrados $x_1$, $x_2$, \ldots, $x_n$ de forma tal que cada $x_i$ posee uno y sólo un vecino en $\{ x_1$, $x_2$, \ldots, $x_{i-1}\}$, para $i=2$, $3$, \ldots, $n$.

Un \emph{esqueleto} $T$ de una gráfica $G$ es una subgráfica generadora de $G$ tal que la intersección de $T$ con cada componente conexa de $G$ es un árbol.

\item Denotemos por $\cp(G)$ el número de vértices de corte de una gráfica $G$.  Prueba que:
\begin{compactitem}
 \item si $e$ es un arista que pertence a un ciclo de $G$ entonces $\cp(G) \leq \cp(G-e)$;
 \item $\cp(G) \leq \cp(T)$ para cualquier esqueleto $T$ de $G$.
 \item $\cp(G) \leq v(G)-2$ y
 \item si $\cp(G)=v(G)-2$ entonces $G$ es una trayectoria.
\end{compactitem}

% \item Prueba que si cualquier par de bloques en una gráfica tienen un vértice en común entonces todos los bloques tienen un vértice en común.

\item Una arista $ab$ es una \emph{diagonal} de un ciclo $C$ si $a$, $b \in V(C)$ y $ab \notin E(C)$.  Prueba que una arista $e$ de un bloque $G$ es una diagonal de un ciclo en $G$ si y sólo si $G-e$ es un bloque.

\item Considera una gráfica conexa $G$ y un vértice $v$ en $G$ tal que $N(v)$ es conexo.  Entonces $G-v$ es conexa.
\item Prueba que si $\delta(G) \geq v(G)-2$ entonces $\kappa(G) = \delta(G)$.

\item Considera $G$ una gráfica conexa no trivial sin vértices de corte.  $X$ y $Y$ dos subconjuntos de vértices de $G$, no necesariamente ajenos, cada uno de cardinalidad al menos dos.  Muestra que existen dos $(X$, $Y)$-trayectorias \textbf{ajenas} en $G$.

\item Considera $G$ una gráfica y $x$, $y$ dos vértices de $G$ no adyacentes (y, por lo tanto, distintos).  Si toda $(x$, $y)$-trayectoria tiene longitud dos entonces
\begin{displaymath}
 \p(x,y)=\cut(x,y)\text{.}
\end{displaymath}

\item En la prueba del Teorema de Menger vista en clase, considera la gráfica $G/Y$ resultante de colapsar $Y$ en un vértice $y$ y $T$ un subconjunto de los vértices de $G/Y$ que no incluya a $y$.  Si existe una $(x$, $y)$-trayectoria $P$ en $G$ que no pase por $T$ entonces la subgráfica $P/Y$ de $G/Y$ contiene una $(x$, $y)$-trayectoria que no pasa por $T$.

\end{enumerate}

\subsubsection*{Extras}
\begin{enumerate}[A.]
 \item  Prueba que un árbol posee exactamente dos hojas si y sólo si es una trayectoria.
 \item Considera $T$ un árbol de orden $k$.  Muestra que si $G$ es una gráfica con $\delta(G) \geq k-1$ entonces $T$ es isomórfico a alguna subgráfica de $G$.
 \item (Vale dos preguntas.) Si $G$ es un bloque tal que $G-a-b$ es disconexa para cualquier par de vértices no adyacentes $a$, $b$.  Prueba que $G$ es un ciclo.
\end{enumerate}


\end{document}