\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}{Siguiente tarea\\8.10 hrs, 5 de noviembre de 2009 (Sin prórroga)}

Dos $(u$, $v)$-trayectorias $P$ y $Q$ son \emph{internamente ajenas} si y sólo si $V(P) \cap V(Q)=\{u$, $v\}$.  $\p(u$, $v)$ denota al máximo número de $(u$, $v)$-trayectorias internamente ajenas en una gráfica, siempre que $u \neq v$ (de otra forma, el número no está definido).  Si $u$ y $v$ están en la misma componente (conexa) de una gráfica $G$, $\cut(u$, $v)$ denota el mínimo número de vértices que debo borrar de $G$ para desconectar a $u$ de $v$.  Nota que $u \neq v$ y $uv$ no es arista de la gráfica, pues de otra forma el número no está definido.  La \emph{conexidad (puntual)} de $G$ se denota por $\kappa(G)$ y se define como:
\begin{displaymath}
 \kappa(G):=\min \{\p(u,v) : u \neq v\}\text{.}
\end{displaymath}

\begin{teorema}[Teorema de Menger]
 Dada una gráfica $G$ y vértices $u$, $v$ no-adyacentes en $G$, el máximo número de $(u$, $v)$-trayectorias internamente ajenas dos a dos es igual al mínimo número de vértices que desconectan a $u$ de $v$, es decir,
\begin{displaymath}
 \p(u,v)=\cut(u,v)\text{.}
\end{displaymath}
\end{teorema}

\begin{teorema}[Teorema de Whitney]
 Si $G$ posee al menos un par de vértices no adyacentes entonces
\begin{displaymath}
 \kappa(G)=\min\{\p(u,v) : u \neq v, uv \notin E(G)\}\text{.}
\end{displaymath}
\end{teorema}

Una gráfica $G$ se dice $k$-conexa si $k \leq \kappa(G)$.

Recuerda, si una gráfica es $k$-conexa entonces siempre que le borre menos de $k$ vértices, la gráfica no se desconecta.  (¿Cómo sería en contrapositiva?)

\begin{enumerate}[1.]
\item Considera $G$ una gráfica $k$-conexa.  Toma $S \subseteq V(G)$ tal que $\lvert S \rvert \geq k$.  Construye la siguiente gráfica $H$.  Primero, agrégale un vértice $y$ que no esté en $G$ y únelo con todos los vértices de $S$, es decir,
\begin{displaymath}
 H:=(V(G) \cup \{ y \}, E(G) \cup \{ yu : u \in S\}\text{.}
\end{displaymath}
Prueba que $H$ es $k$-conexa.  (\emph{Sugerencia.}  Prueba que al quitar
cualquier conjunto de $k-1$ vértices, la gráfica no se desconecta.)

Si $X$, $Y$ son subconjuntos de vértices de $G$, una $(X$, $Y)$-trayectoria $P$ es una trayectoria en $G$ cuyo vértice inicial pertenece a $X$ y cuyo vértice final pertenece a $Y$.

\item Considera $G$ una gráfica y $X$, $Y$ subconjuntos de vértices de $G$ con al menos $k$ vértices cada uno.  Entonces existe una familia de $k$ $(X$, $Y)$-trayectorias ajenas en $G$.

Una familia de $k$ $(x$, $Y)$-trayectorias internamente ajenas cuyos vértices terminales son diferentes es conocido como un $k$-ventilador (\textit{$k$-fan}) de $x$ a $Y$.

\item Considera $G$ una gráfica $k$-conexa, $x$ un vértice de $G$ y $Y \subseteq V(G) \setminus \{ x \}$ un conjunto de al menos $k$ vértices de $G$.  Entonces existe un $k$-ventilador en $G$ de $x$ a $Y$.

\item Si $S$ es un conjunto de $k$ vértices en una gráfica $k$-conexa $G$, con $k \geq 2$, entonces existe un ciclo que contiene todos los vértices de $S$.  Prueba lo siguiente:

\begin{enumerate}
 \item Pruébalo por inducción.  Primero, para $k=2$.
 \item Supón que $k \geq 3$.  Considera $x \in S$ y define $T:=S\setminus \{x\}$.
 \item $G$ es $(k-1)$-conexa.  ¿Por qué existe un ciclo $C$ tal que $T \subseteq V(C)$?
 \item Define $Y:= V(C)$.  Podemos suponer que $x \notin Y$, ¿por qué?
 \item Si $\lvert Y \rvert \geq k$ entonces existe un $k$-ventilador de $x$ a $Y$, ¿por qué?
 \item $T$ divide a $C$ en $k-1$ segmentos ajenos en aristas (argumenta).
 \item Dos extremos del ventilador, $P$ y $Q$, terminan en el mismo segmento.  ¿Por qué?
 \item Muestra el ciclo pedido.
 \item Si $\lvert Y \rvert = k-1$, construye un ventilador adecuado y muestra el ciclo.
 \item ¿Puede pasar que $\lvert Y \rvert \leq k-1$?
 \item Concluye.
\end{enumerate}

\item Prueba que toda gráfica $3$-conexa no bipartita tiene al menos cuatro ciclos de longitud impar.
\end{enumerate}

\subsubsection*{Extras}
\begin{enumerate}[A.]
\item Muestra que si $G$ es $k$-conexa y $e$ es cualquier arista de $G$ entonces $G/e$ (colapsar la arista $e$) es $(k-1)$-conexa.
\item Para cada $k \geq 4$, encuentra una gráfica $k$-conexa $G$ diferente de $K_{k+1}$ tal que $\kappa(G/e)=k-1$ para toda arista $e$ de $G$.
\end{enumerate}

\end{document}