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

% \addtolength{\voffset}{-2cm}
% \addtolength{\textheight}{3cm}
% \addtolength{\textwidth}{1.5cm}
% \addtolength{\hoffset}{-0.5cm}
% \addtolength{\textwidth}{2cm}

\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{\mcd}{mcd}
\DeclareMathOperator{\exc}{e}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\cc}{cc}
\DeclareMathOperator{\Q}{Q}
\DeclareMathOperator{\domatic}{d}

\begin{document}
\header{Teoría de las Gráficas II}{Octava tarea}

\begin{proposicion}
\label{271}
Considera $D$ una digráfica cuasitransitiva. Supón que $P=(x_1$, $x_2$, \ldots, $x_k)$ es una $(x_1$, $x_k)$-trayectoria minimal. Entonces la subdigráfica inducida por $V(P)$ es semicompleta y $x_j \rightarrow x_1$ para todo $2 \leq i+1 <j \leq k$, excepto para $k=4$, caso en el que la flecha entre $x_1$ y $x_k$ puede no existir.
\end{proposicion}

\begin{corolario}
\label{272}
Si una digráfica cuasitransitiva $D$ posee una $(x$, $y)$-trayectoria pero $x$ no domina $y$, entonces $y \rightarrow x$ ó existen vértices $u$, $v$ en $V(D) \setminus \{ x$, $y\}$ tales que $x \rightarrow u \rightarrow v \rightarrow y$ y $y \rightarrow u \rightarrow y \rightarrow x$.
\end{corolario}

\begin{lema}
\label{273}
Supón que $A$ y $B$ son componentes fuertemente conexas distintas de una digráfica cuasitransitiva $D$ con al menos una flecha de $A$ hacia $B$.  Entonces $A \mapsto B$.
\end{lema}






\begin{enumerate}
\item Prueba que todo torneo de orden $n \geq 2k+2$ posee un vértice de exgrado al menos $k+1$.
\item Prueba que todo torneo fuertemente conexo de orden $n$ posee ciclos de longitud $3$, $4$, \ldots, $n-1$, $n$.
\item Prueba que si un torneo tiene al menos un ciclo entonces tiene al menos dos trayectorias hamiltonianas.
\item 

\begin{lema}
\label{274}
Considera $D$ una digráfica cuasitransitiva fuertemente conexa con al menos dos vértices. Entonces se tiene lo siguiente:
\begin{enumerate}
 \item $\overline{UG(D)}$ es disconexa y
 \item si $S$ y $S'$ son dos subdigráficas de $D$ tales que $\overline{UG(S)}$ y $\overline{UG(S')}$ son componentes conexas distintas de $\overline{UG(D)}$ entonces $S \mapsto S'$, $S' \mapsto S$ o se tienen que tanto $S \rightarrow S'$ y $S' \rightarrow S$, en cuyo caso $\lvert V(S) \rvert = \lvert V(S') \rvert =1$.
\end{enumerate}
\end{lema}

Prueba primero el inciso (b).

Para el inciso (a), hazlo por inducción.  Considera un vértice $z$ en $D$, hay dos casos posibles: $D - z$ no es fuertemente conexa o $D-z$ sí es fuertemente conexa.  Para el primer caso puedes pensar en las componentes fuertemente conexas de $D-z$, ¿qué flechas hay entre las componentes fuertemente conexa iniciales y finales de $D-z$ y $z$?  Lo anterior y el Lema~\ref{273} implican que si $X$ es una componente fuertemente conexa inicial de $D-z$ y $Y$ es final entonces $X \mapsto Y$. ¿Cómo son las componentes fuertemente conexas no iniciales ni terminales de $D-z$ con respecto a las iniciales y a las terminales? Deduce que $z$ es adyacente a todo vértice de $V(D)\setminus z$ y lo que querías probar.  Si $D-z$ es fuertemente conexa entonces argumenta por que existe una flecha $z \rightarrow w$ de $z$ a $D-z$. Usa la hipótesis inductiva sobre $D-z$. Argumenta porque puedes escoger subdigráficas $S$ y $S'$ de $D$ tales que $w \in S$ y $S \mapsto S'$. Finalmente prueba que $z$ es completamente adyacente a $S'$ y concluye.

\item
\begin{teorema}
Considera $D$ una digráfica cuasitransitiva.
\begin{enumerate}
\item Si $D$ no es fuertemente conexa entonces existen una gráfica transitiva $T$ con vértice $\{u_1$, $u_2$, \ldots, $u_t\}$ y digráficas cuasitransitivas fuertemente conexas $H_1$, $H_2$, \ldots, $H_t$ tales que $D = T[H_1$, $H_2$, \ldots, $H_t]$. donde $H_i$ se substituye por $u_i$ para $i=1$, $2$, \ldots, $t$.
\item Si $D$ es fuertemente conexa entonces existen una digráfica semicompleta $S$ con vértices $\{v_1$, $v_2$, \ldots, $v_s\}$ y digráficas cuasitransitivas $Q_1$, $Q_2$, \ldots, $Q_s$ tales que $Q_i$ es un vértice o no es fuertemente conexa y $D=S[Q_1$, $Q_2$, \ldots, $Q_s]$, donde  $Q_i$ se substuye por $v_i$, para $i = 1$, $2$, \ldots, $s$.
\end{enumerate}
\end{teorema}
Para el primer inciso, basta considerar el Lema~\ref{273}. Para el segundo, el Lema~\ref{274}.
\end{enumerate}
\end{document}