\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{graphicx}
\usepackage{color} 
\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{\mcd}{mcd}

\begin{document}
\header{Teoría de Gráficas}{Cuarta tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas\hyphenation{res-pues-tas}. Se entrega en equipos de exactamente dos personas.

\begin{enumerate}
 \item \begin{enumerate} 
   \item Considera una gráfica $G$ de orden par $n \geq 6$ tal que todo vértice tiene grado tres o cuatro. Si $G$ posee dos árboles generadores $T_1$ y $T_2$ tales que $\{A(T_1)$, $A(T_2)\}$ es una partición de $A(G)$, ¿cuántos vértices de grado cuatro tiene $G$?
   \item Muestra que existen un entero par $n \geq 6$ y una gráfica conexa $G$ de orden $n$ tal que \begin{enumerate}
    \item Cada vértice de $G$ tiene grado tres o cuatro.
    \item $G$ posee el número de vértices de grado cuatro determinados arriba y
    \item $G$ \textbf{no} posee dos árboles generadores $T_1$ y $T_2$ tales que $\{A(T_1)$, $A(T_2)\}$ es una partición de $A(G)$.
   \end{enumerate}
   \end{enumerate}
 \item Prueba que si $G$ es $k$-conexa entonces $G+K_1$ es $(k+1)$-conexa.
 \item ¿Cuál es el menor tamaño posible de una gráfica $k$-conexa de orden $n$?
 \item Considera un vértice $v$ en una gráfica $G$, prueba que $\kappa(G-v)$ es igual a $\kappa(G)$ o a $\kappa(G)-1$.
 \item Considera una arista $e$ en una gráfica $G$, prueba que $\kappa(G-e)$ es igual a $\kappa(G)$ o a $\kappa(G)-1$.
 \item Prueba que $\kappa(G)=\min \{ \kappa_G(u$, $v)$ : $u$, $v \in V(G)$ y $uv \notin A(G)\}$.
 \item Considera una gráfica $G$  $k$ conexa, $k \geq 1$, y $S$ es cualquier conjunto de $k$ vértices de $G$. Prueba que si $H$ es la gráfica resultante de añadir un nuevo vértice a $G$ y hacerlo adyacente a cada uno de los vérties de $S$ entonces $H$ también es $k$-conexa.
 \item Prueba que si $G$ es una gráfica $k$-conexa, $k \geq 2$, y $u$, $v_1$, $v_2$, \ldots, $v_t$ son $t+1$ vértices distintos de $G$, con $2 \leq t \leq k$, entonces $G$ posee una $(u$, $v_i)$-trayectoria para cada $i \in \{1$, $2$, \ldots, $t\}$, tal que cualquier par de esas de esas trayectorias sólo tienen a $u$ en común.
 \item Prueba que:
 \begin{teorema}
  Si $G$ es una gráfica $k$-conexa, $k \geq 2$, entonces para cualquier conjunto de $k$ vértices están en un ciclo en común de $G$.
 \end{teorema}

\begin{proof}
 Tomemos $S=\{v_1$, $v_2$, \ldots, $v_k\}$ un conjunto de $k$ vértices de $G$. Entre todos los ciclos de $G$, sea $C$ uno que contenga un número máximo $p$ de vértices de $S$. Entonces $p \geq k$. Si $p=k$, ya está, por lo que podemos suponer que $p < k$. Ya que $G$ es $k$-conexa, $G$ en particular es $2$-conexa y, como probamos en clase, $p \geq 2$. Podemos suponer que $v_1$, $v_2$, \ldots, $v_p$ están en $C$. Sea $u$ un vértices de $S$ que no esté en $C$. Consideremos dos casos.
 
 \textit{Caso 1}. El ciclo $C$ contiene exactamente $p$ vértices, digamos que $C=(v_1$, $v_2$, \ldots, $v_p$, $v_1)$. Con los resultados previos, llega a una contradicción.
 
 \textit{Caso 2}. El ciclo $C$ contiene al menos $p+1$ vértices. Escoge algún vértice $v_0$ en $C$ que no pertenezca a $S$. Prueba que hay una $(u$, $v_i)$-trayectoria $P_i$ por cada $i\in \{0$, $1$, \ldots, $p\}$ tal que dos a dos sólo se intersectan en $u$. Para cada $P_i$, llama $u_i$ al último vértice de $C$ en $P_i$. Supón que los vértices $u_i$ están ordenados de forma consecutiva en el ciclo módulo $p$. Prueba que hay un $i$ tal que la trayectoria $C[u_i$, $u_{i+1}]$ (con $i+1$ módulo $p$) que no puede contener ningún vértice de $S$ excepto por los extremos. Con los resultados previos, llega a una contradicción.
\end{proof}

 
\end{enumerate}
\end{document}