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

\begin{document}
\header{Teoría de las Gráficas}{Sétima tarea\\21 de mayo de 2009}
 
\begin{lema}
Si $v_1$, $v_2$, \ldots, $v_n$ son $n$ vértices distintos de una gráfica $G$ $n$-conexa entonces la gráfica $H$ construida a partir de $G$ al añadir un vértice de grado $n$ que es adyacente a cada uno de los vértices $v_1$, $v_2$, \ldots, $v_n$ es $n$-conexa.
\end{lema}

\begin{teorema}[Teorema de Menger]
Si $u$ y $v$ son vértices no adyacentes en una gráfica $G$ entonces el mínimo número de vértices que separan $u$ y $v$ es igual al máximo número de $(u$, $v)$-trayectorias internamente ajenas en $G$.
\end{teorema}


\begin{teorema}[Teorema de Whitney]
Una gráfica no trivial $G$ es $n$-conexa si y sólo si para cada par $u$, $v$ de vértices distintos existen al menos $n$ $(u$, $v)$-trayectorias internamente ajenas en $G$.
\end{teorema}


\begin{enumerate}[1.]
 \item Prueba que si $B_1$ y $B_2$ son bloques tales que $B_1 \cap B_2 \neq \emptyset$ entonces $\lvert B_1 \cap B_2 \rvert = 1$ y la intersección es un punto de corte.
 \item Si $G$ es conexa, prueba que la gráfica de bloques-vértices de corte es un árbol.
 \item Define la \emph{conexidad lineal local} para vértices $u$ y $v$, $\lambda_G(u,v)$, y demuestra que:
\begin{enumerate}
 \item $\lambda_G(u,v) \leq 1$ implica que $\kappa_G(u,v) \leq 1$ siempre que $u$ y $v$ no sean adyacentes;
 \item $\lambda_G(u,v)\leq \min\{ d_G(u)$, $d_G(v)\}$ y
 \item si $u$ no es adyacente a $v$ entonces $\kappa_G(u$, $v) \leq \lambda_G(u$, $v)$.
\end{enumerate}
 \item Usa el Teorema de Menger para probar que $\kappa(G)=\lambda(G)$ cuando $G$ es $3$-regular.
 \item Prueba que si $e \in A(G)$ entonces $\kappa(G)-1 \leq \kappa(G-e)$.
 \item Prueba que si $e \in A(G)$ entonces $\kappa_{G-e}(a,b) \geq \kappa(G)$.
 \item Usa el ejercicio previo para probar el Teorema de Whitney.
 \item Prueba que una gráfica $G$ de orden $p \geq 2n$ es $n$-conexa si y sólo si para cualesquiera dos conjuntos ajenos $V_1$ y $V_2$ de $n$ vértices cada uno, existen $n$ trayectorias ajenas que conectan $V_1$ y $V_2$.
\end{enumerate}

\begin{enumerate}[A.]
 \item[Extra.] Prueba que una gráfica $G$ de orden $p \geq n+1 \geq 3$ es $n$-conexa si y sólo si para cada conjunto $S$ de $n$ vértices distintos de $G$ y para cada subconjunto $T$ de $S$ de dos vértices, existe un ciclo de $G$ que contiene los vértices de $T$ pero no los vértices $S \setminus T$.
\end{enumerate}
 
\end{document}