\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 II}{Tarea tercera}



\begin{enumerate}[1.]
 \item Da el valor de $\chi'(K_n)$ y pruébalo, para cualquier entero $n$
positivo.

 \item Usa el teorema visto en clase para probar el Teorema de Vizing-Gupta.
\begin{teorema}[Teorema de Vizing-Gupta]
 El número cromático lineal de cualquier gráfica es $\Delta$ ó $\Delta+1$.
\end{teorema}

\item Supongamos que $q$ denota el número de aristas de una gráfica.  Prueba
que:
\begin{enumerate}
 \item para cualquier gráfica, $\alpha' \geq \frac{q}{\Delta+1}$ y que
 \item para cualquier gráfica bipartita con $\Delta \geq 1$, $\alpha' \geq
\frac{q}{\Delta}$.
\end{enumerate}

\item Usa el Teorema de König sobre coloración de aristas para probar que toda
gráfica bipartita $k$-regular con $k \geq 1$ posee un apareamiento perfecto.

Sea $G$ cualquier gráfica bipartita y $M$ cualquier apareamiento en $G$.
Supondremos que los vértices de $G$ están acomodados en dos líneas, una encima
de la otra, y que cada arista tiene un extremo en cada línea.

La \emph{digráfica coloreada} $D$ correspondiente a $M$ se construye con las
siguientes reglas:

\textbf{Dirección de las aristas}.  Asignemos una dirección a cada aristas de
$G$.  Las flechas correspondientes aristas en $M$ van para arriba.  Las otras,
para abajo.

Esto nos arroja una digráfica a partir de la gráfica $G$.  Observa que todo
camino dirigido en esta digráfica alterna entre aristas para arriba y aristas
para abajo y, por lo tanto, alterna entre aristas que están en $M$ y aristas
que no están en $M$.

\textbf{Coloración de los vértices}.  Los vértices saturados en la línea de
arriba son azules, los vértices saturados abajo son rojos y todos los vértices
no saturados son verdes.

Construyamos el siguiente conjunto de vértices de $S$ de $D$: $S$ contiene
todos los vértices verdes, todos los vértices azules que se pueden alcanzar en
$D$ desde algún vértice verde (por medio de una trayectoria dirigida) y todos
los vértices rojos que no se pueden alcanzar en $D$ desde algún vértice verde.

En general, el conjunto $S$ construido a partir de un apareamiento dado es
independiente si y sólo si el apareamiento es maximal.  Más aún, siempre que el
apareamiento no sea maximal existe un algoritmo simple que lo crece.

Dado $P$ una trayectoria de un vértice verde a otro vértice verde en la
digráfica coloreada construida a partir del apareamiento dado $M$ en una
gráfica bipartita entonces $M$ puede ser aumentada a un apareamiento más grande
quitando todos las aristas de $M$ en $P$ y añadiendo todas las aristas de $P$
que no están en $M$.

\item ¿Por qué funciona el algoritmo previo?  Prueba que obtienes un
apareamiento y que contiene una arista más que $M$.

El algoritmo anterior prueba cómo un apareamiento no maximal puede ser
aumentado siempre que existe una trayectoria de un vértice verde a otro vértice
verde en la digráfica coloreada correspondiente.  Sin embargo, ¿esa trayectoria
siempre existe?

\begin{teorema}
 Las siguientes tres condiciones son equivalentes: 
\begin{enumerate}[(i)]
\item $M$ es maximal,
\item $D$ no contiene una trayectoria entre dos vértices verdes y
\item $S$ es un conjunto independiente.
\end{enumerate}
\end{teorema}

\item Prueba que (i) implica (ii).
\item Prueba que (ii) implica (iii).  Considera todas las posibilidades de
vértices que pueden ser adyacentes en $S$: verde y verde, verde y rojo, azul y
verde, azul y rojo unidos por una flecha que ve hacia arriba y azul y rojo
unidos por una flecha que ve hacia abajo.
\item Prueba que (iii) implica (i).  Si $S$ es independiente entonces $M$ es
maximal.  Muestra que:
\begin{enumerate}
 \item $\alpha' \geq p-q$ y $\alpha' \geq m$
 \item La igualdad debe darse en el ítem anterior, ¿por qué?
 \item ¿Por qué esto muestra que $M$ es maximal?
\end{enumerate}

 \item Por lo tanto, tenemos el Teorema de König-Egervary.

 \item En cualquier representación plana de una gráfica bipartita aplanable,
todos los grados de las caras deben ser pares.  ¿Por qué?

 \item Muestra que no puede existir una gráfica bipartita $4$-regular plana.

 \item \begin{enumerate}[(a)]
 \item Encuentra un ejemplo de una gráfica conexa que
posee $(4,4,4,4,4,2,\ldots)$ como sucesión de vértices pero no es una
subdivisión de $K_5$ (diferente de Petersen).
 \item La misma pregunta pero para $(3,3,3,3,3,3,2,\ldots)$ y $K_{3,3}$.
\end{enumerate}

\item Muestra que $S$ es un conjunto independiente en una gráfica $G$ si y sólo
si $V(G) \setminus S$ es una cubierta de $G$.

\item Muestra que para todo $k$ y todo $l$ enteros positivos,
\begin{displaymath}
 r(k,l)=r(l,k)\text{.}
\end{displaymath}

\item Prueba que para todos los enteros positivos $t_i$, $i \in \{1$, $2$,
\ldots, $k\}$,
\begin{displaymath}
 r(t_1, t_2, \ldots, t_k)\leq r(t_1-1, t_2, \ldots, t_k) + r(t_1, t_2-1, \ldots,
t_k)+\ldots+r(t_1, t_2, \ldots, t_k-1)-k+2\text{.}
\end{displaymath}

\item Supón que queremos encontrar un flujo maximal en una red con múltiples
fuentes o pozos.  ¿Qué significa?  Cómo puedes resolver el problema:
\begin{enumerate}[(a)]
 \item añadiendo algo a la red,
 \item sin añadir nada a la red.
\end{enumerate}
\end{enumerate}

% \subsubsection*{Extras}
% \begin{enumerate}[A.]
% \item Considera $G$ una gráfica de orden ocho y
% tamaño diez con un paseo euleriano cerrado.
% \end{enumerate}
\end{document}