\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}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\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}{Sexta tarea}
% Se entrega el viernes 16 de abril. Todos los ejercicios bien justificados.
\vspace{0.5cm}


\begin{enumerate}
 \item Prueba que el conjunto de las aristas de cualquier gráfica conexa sin un paseo euleriano cerrado se pueden partir en un conjunto de paseos abiertos (cuyo número es la mitad de los vértices de grado impar).
 \item Encuentra un ciclo hamiltoniano en cada una de las gráficas siguientes.
\begin{figure}[!h]
\definecolor{qqqqff}{rgb}{0,0,1}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.5cm,y=0.5cm]
% \clip(-2.8,-0.04) rectangle (16.48,11.62);
\draw (2,10)-- (1,9);
\draw (1,9)-- (1,8);
\draw (1,8)-- (2,7);
\draw (2,7)-- (3,7);
\draw (3,7)-- (4,8);
\draw (4,8)-- (4,9);
\draw (4,9)-- (3,10);
\draw (3,10)-- (3,7);
\draw (2,7)-- (2,10);
\draw (1,9)-- (4,9);
\draw (1,8)-- (4,8);
\draw (1,9)-- (3,7);
\draw (2,7)-- (4,9);
\draw (1,8)-- (3,10);
\draw (2,10)-- (4,8);
\draw (5,9.32)-- (5.78,8.54);
\draw (5.78,8.54)-- (6.54,7.64);
\draw (6.54,7.64)-- (7.36,6.7);
\draw (5,7.7)-- (5.78,8.54);
\draw (6.5,9.32)-- (7.32,10.18);
\draw (6.5,9.32)-- (5.78,8.54);
\draw (5.76,6.76)-- (6.54,7.64);
\draw (7.24,8.46)-- (6.54,7.64);
\draw (7.24,8.46)-- (8,9.3);
\draw (5.8,10.16)-- (6.5,9.32);
\draw (7.24,8.46)-- (8.02,7.66);
\draw (7.24,8.46)-- (6.5,9.32);
\draw (5,7.7)-- (7.36,6.7);
\draw (5.76,6.76)-- (8.02,7.66);
\draw (5,9.32)-- (7.32,10.18);
\draw (5.8,10.16)-- (8,9.3);
\draw (5,9.32)-- (5,7.7);
\draw (8,9.3)-- (8.02,7.66);
\draw (5.8,10.16)-- (5,9.32);
\draw (7.32,10.18)-- (8,9.3);
\draw (5,7.7)-- (5.76,6.76);
\draw (7.36,6.7)-- (8.02,7.66);
\draw (1,4)-- (1,3);
\draw (2,5)-- (2.52,3.52);
\draw (2.52,3.52)-- (3,2);
\draw (2,2)-- (2.52,3.52);
\draw (2.52,3.52)-- (3,5);
\draw (4,4)-- (4,3);
\draw (1,4)-- (2,2);
\draw (3,2)-- (4,4);
\draw (1,4)-- (2.52,3.52);
\draw (1,3)-- (3,2);
\draw (2,2)-- (4,3);
\draw (1,4)-- (4,4);
\draw (2,5)-- (3,5);
\draw (2,5)-- (1,3);
\draw (2,5)-- (4,3);
\draw (3,5)-- (4,3);
\draw (7.48,3.84)-- (8,2.82);
\draw (8,2.82)-- (8.56,3.84);
\draw (8.56,3.84)-- (7.48,3.84);
\draw (7.48,3.84)-- (8,5);
\draw (8,5)-- (8.56,3.84);
\draw (8.56,3.84)-- (9.18,2.78);
\draw (9.18,2.78)-- (8,2.82);
\draw (8,2.82)-- (6.82,2.8);
\draw (6.82,2.8)-- (7.48,3.84);
\draw (6.82,2.8)-- (8,2);
\draw (8,2)-- (8,2.82);
\draw (8,2)-- (9.18,2.78);
\draw (6.8,4.22)-- (6.82,2.8);
\draw (6.8,4.22)-- (8,5);
\draw (8,5)-- (9.16,4.16);
\draw (9.16,4.16)-- (9.18,2.78);
\draw (8.56,3.84)-- (9.16,4.16);
\draw (7.48,3.84)-- (6.8,4.22);
\draw (6,2)-- (6.8,4.22);
\draw (6,2)-- (6.82,2.8);
\draw (6,2)-- (8,2);
\draw (8,2)-- (10,2);
\draw (10,2)-- (9.18,2.78);
\draw (10,2)-- (9.16,4.16);
\draw (6.8,4.22)-- (8,6);
\draw (8,6)-- (8,5);
\draw (8,6)-- (9.16,4.16);
\draw(8,3.5) circle (1.25cm);
\fill [color=qqqqff] (1,8) circle (1.5pt);
\fill [color=qqqqff] (1,9) circle (1.5pt);
\fill [color=qqqqff] (2,7) circle (1.5pt);
\fill [color=qqqqff] (3,7) circle (1.5pt);
\fill [color=qqqqff] (4,8) circle (1.5pt);
\fill [color=qqqqff] (4,9) circle (1.5pt);
\fill [color=qqqqff] (3,10) circle (1.5pt);
\fill [color=qqqqff] (2,10) circle (1.5pt);
\fill [color=qqqqff] (5,9.32) circle (1.5pt);
\fill [color=qqqqff] (5,7.7) circle (1.5pt);
\fill [color=qqqqff] (6.5,9.32) circle (1.5pt);
\fill [color=qqqqff] (6.54,7.64) circle (1.5pt);
\fill [color=qqqqff] (8.02,7.66) circle (1.5pt);
\fill [color=qqqqff] (8,9.3) circle (1.5pt);
\fill [color=qqqqff] (5.78,8.54) circle (1.5pt);
\fill [color=qqqqff] (7.24,8.46) circle (1.5pt);
\fill [color=qqqqff] (5.8,10.16) circle (1.5pt);
\fill [color=qqqqff] (7.32,10.18) circle (1.5pt);
\fill [color=qqqqff] (5.76,6.76) circle (1.5pt);
\fill [color=qqqqff] (7.36,6.7) circle (1.5pt);
\fill [color=qqqqff] (1,4) circle (1.5pt);
\fill [color=qqqqff] (1,3) circle (1.5pt);
\fill [color=qqqqff] (2,2) circle (1.5pt);
\fill [color=qqqqff] (2,5) circle (1.5pt);
\fill [color=qqqqff] (3,5) circle (1.5pt);
\fill [color=qqqqff] (3,2) circle (1.5pt);
\fill [color=qqqqff] (4,3) circle (1.5pt);
\fill [color=qqqqff] (4,4) circle (1.5pt);
\fill [color=qqqqff] (2.52,3.52) circle (1.5pt);
\fill [color=qqqqff] (6,2) circle (1.5pt);
\fill [color=qqqqff] (8,2) circle (1.5pt);
\fill [color=qqqqff] (10,2) circle (1.5pt);
\fill [color=qqqqff] (6.82,2.8) circle (1.5pt);
\fill [color=qqqqff] (8,2.82) circle (1.5pt);
\fill [color=qqqqff] (9.18,2.78) circle (1.5pt);
\fill [color=qqqqff] (7.48,3.84) circle (1.5pt);
\fill [color=qqqqff] (8.56,3.84) circle (1.5pt);
\fill [color=qqqqff] (8,5) circle (1.5pt);
\fill [color=qqqqff] (8,6) circle (1.5pt);
\fill [color=qqqqff] (6.8,4.22) circle (1.5pt);
\fill [color=qqqqff] (9.16,4.16) circle (1.5pt);
\end{tikzpicture}
\end{figure}
 \item Considera $m$ y $n$ enteros positivos. ¿Qué deben cumplir $m$ y $n$ para que tenagamos que
 \begin{enumerate}[(a)]
  \item $K_{m,n}$ posea un ciclo hamiltoniano?
  \item $K_{m,n}$ posea una tryaectoria hamiltoniana?
 \end{enumerate}
 \item Aplica el criterio de la subgráfica a cada una de las gráficas siguientes. En cada caso, ¿cuál es la conclusión?
\begin{figure}[!h]
\definecolor{qqqqff}{rgb}{0,0,1}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.75cm,y=0.75cm]
% \clip(-1.32,-1.24) rectangle (17.96,10.42);
\draw (1,3)-- (1,1);
\draw (1,1)-- (2,2);
\draw (2.5,2.5)-- (2,2);
\draw (2.5,2.5)-- (3,3);
\draw (2,2)-- (2.5,1.5);
\draw (2.5,1.5)-- (3,1);
\draw (3,1)-- (3.5,1.5);
\draw (3.5,1.5)-- (4,2);
\draw (4,2)-- (3.5,2.5);
\draw (3.5,2.5)-- (3,3);
\draw (3,3)-- (1,3);
\draw (3,3)-- (5,3);
\draw (5,3)-- (5,1);
\draw (5,1)-- (4,2);
\draw (4,2)-- (5,3);
\draw (2,2)-- (1,3);
\draw (1,1)-- (3,1);
\draw (3,1)-- (5,1);
\draw (2.5,2.5)-- (3,1);
\draw (3,1)-- (3.5,2.5);
\draw (3,3)-- (3.5,1.5);
\draw (2.5,1.5)-- (3,3);
\draw (5.82,1.98)-- (7,2);
\draw (8,2)-- (7,2);
\draw (8,2)-- (9,2);
\draw (9,2)-- (10,2);
\draw (5.82,1.98)-- (8,1);
\draw (8,1)-- (10,2);
\draw (10,2)-- (8,3);
\draw (8,3)-- (5.82,1.98);
\draw (7,2)-- (7.68,2.28);
\draw (7.68,2.28)-- (8,3);
\draw (8,3)-- (8.26,2.28);
\draw (8.26,2.28)-- (9,2);
\draw (9,2)-- (8.26,1.68);
\draw (8.26,1.68)-- (8,1);
\draw (8,1)-- (7.7,1.7);
\draw (7.7,1.7)-- (7,2);
\draw (7.68,2.28)-- (8,2);
\draw (8,2)-- (7.7,1.7);
\draw (8,2)-- (8.26,1.68);
\draw (8,2)-- (8.26,2.28);
\draw (2,4)-- (2.5,4);
\draw (2.5,4)-- (3,4);
\draw (3,4)-- (3.5,4);
\draw (3.5,4)-- (4,4);
\draw (4,4)-- (3.76,4.5);
\draw (3.5,5)-- (3.76,4.5);
\draw (3.26,5.5)-- (3.5,5);
\draw (3,6)-- (3.26,5.5);
\draw (3,6)-- (2.74,5.5);
\draw (2.74,5.5)-- (2.5,5.02);
\draw (2.5,5.02)-- (2.24,4.5);
\draw (2.24,4.5)-- (2,4);
\draw (2.24,4.5)-- (2.5,4);
\draw (2.74,5.5)-- (3.26,5.5);
\draw (3.76,4.5)-- (3.5,4);
\draw (2.5,5.02)-- (3,5);
\draw (3.5,5)-- (3,5);
\draw (2.74,4.5)-- (2.5,5.02);
\draw (2.74,4.5)-- (3,4);
\draw (3,4)-- (3.26,4.5);
\draw (3.26,4.5)-- (3.5,5);
\draw (3,5)-- (3.26,4.5);
\draw (3.26,4.5)-- (2.74,4.5);
\draw (2.74,4.5)-- (3,5);
\draw (6.02,5.5)-- (9.98,5.5);
\draw (6,4.5)-- (10,4.5);
\draw (8,5.5)-- (9,3.5);
\draw (8,4.5)-- (8.98,6.5);
\draw (8,5.5)-- (7,4.52);
\draw (8.98,6.5)-- (8,5.5);
\draw (7,5.5)-- (8,4.5);
\draw (8,4.5)-- (9,3.5);
\draw (6,4.5)-- (7,3.5);
\draw (8,4.5)-- (7,3.5);
\draw (6,4.5)-- (7,6.5);
\draw (6.02,5.5)-- (7,3.5);
\draw (6,4.5)-- (6.02,5.5);
\draw (6.02,5.5)-- (7,6.5);
\draw (8.98,6.5)-- (9.98,5.5);
\draw (7,6.5)-- (8,5.5);
\draw (9,5.48)-- (10,4.5);
\draw (9.98,5.5)-- (9,4.5);
\draw (9,3.5)-- (10,4.5);
\fill [color=qqqqff] (1,1) circle (1.5pt);
\fill [color=qqqqff] (2,2) circle (1.5pt);
\fill [color=qqqqff] (3,1) circle (1.5pt);
\fill [color=qqqqff] (4,2) circle (1.5pt);
\fill [color=qqqqff] (5,1) circle (1.5pt);
\fill [color=qqqqff] (2.5,1.5) circle (1.5pt);
\fill [color=qqqqff] (3.5,1.5) circle (1.5pt);
\fill [color=qqqqff] (3,3) circle (1.5pt);
\fill [color=qqqqff] (2.5,2.5) circle (1.5pt);
\fill [color=qqqqff] (3.5,2.5) circle (1.5pt);
\fill [color=qqqqff] (1,3) circle (1.5pt);
\fill [color=qqqqff] (5,3) circle (1.5pt);
\fill [color=qqqqff] (5.82,1.98) circle (1.5pt);
\fill [color=qqqqff] (7,2) circle (1.5pt);
\fill [color=qqqqff] (8,2) circle (1.5pt);
\fill [color=qqqqff] (9,2) circle (1.5pt);
\fill [color=qqqqff] (10,2) circle (1.5pt);
\fill [color=qqqqff] (8,1) circle (1.5pt);
\fill [color=qqqqff] (8,3) circle (1.5pt);
\fill [color=qqqqff] (7.68,2.28) circle (1.5pt);
\fill [color=qqqqff] (8.26,2.28) circle (1.5pt);
\fill [color=qqqqff] (7.7,1.7) circle (1.5pt);
\fill [color=qqqqff] (8.26,1.68) circle (1.5pt);
\fill [color=qqqqff] (3,4) circle (1.5pt);
\fill [color=qqqqff] (2.5,4) circle (1.5pt);
\fill [color=qqqqff] (3.5,4) circle (1.5pt);
\fill [color=qqqqff] (4,4) circle (1.5pt);
\fill [color=qqqqff] (2,4) circle (1.5pt);
\fill [color=qqqqff] (2.24,4.5) circle (1.5pt);
\fill [color=qqqqff] (2.74,4.5) circle (1.5pt);
\fill [color=qqqqff] (3.26,4.5) circle (1.5pt);
\fill [color=qqqqff] (3.76,4.5) circle (1.5pt);
\fill [color=qqqqff] (2.5,5.02) circle (1.5pt);
\fill [color=qqqqff] (3,5) circle (1.5pt);
\fill [color=qqqqff] (3.5,5) circle (1.5pt);
\fill [color=qqqqff] (2.74,5.5) circle (1.5pt);
\fill [color=qqqqff] (3.26,5.5) circle (1.5pt);
\fill [color=qqqqff] (6,4.5) circle (1.5pt);
\fill [color=qqqqff] (7,4.52) circle (1.5pt);
\fill [color=qqqqff] (8,4.5) circle (1.5pt);
\fill [color=qqqqff] (9,4.5) circle (1.5pt);
\fill [color=qqqqff] (10,4.5) circle (1.5pt);
\fill [color=qqqqff] (3,6) circle (1.5pt);
\fill [color=qqqqff] (6.02,5.5) circle (1.5pt);
\fill [color=qqqqff] (7,5.5) circle (1.5pt);
\fill [color=qqqqff] (8,5.5) circle (1.5pt);
\fill [color=qqqqff] (9,5.48) circle (1.5pt);
\fill [color=qqqqff] (9.98,5.5) circle (1.5pt);
\fill [color=qqqqff] (7,6.5) circle (1.5pt);
\fill [color=qqqqff] (7,3.5) circle (1.5pt);
\fill [color=qqqqff] (9,3.5) circle (1.5pt);
\fill [color=qqqqff] (8.98,6.5) circle (1.5pt);
\end{tikzpicture}
\end{figure}
 \item Explica por qué el cirterio negativo para gráficas bipartitas puede ser pensado como un caso especial del criterio de la subgraica.
 \item ¿Cuáles de las sucesion siguientes satisfacen la condición de los grados de Pósa?
 \begin{enumerate}
  \item $(2,2,3,4,4,5)$
  \item $(2,2,3,4,4,5,5)$
  \item $(4,5,5,5,5,6,6,6,6,6)$
  \item $(4,5,5,5,5,6,6,6,6,6,6)$
 \end{enumerate}
 \item Si Muestra que si una gráfica satisface la condición de Dirac de que cada vértice tenga grado igual o mayor que $n/2$ entonces satisface la condición de Pósa.
 \item Muestra que toda gráfica que tenga sucesión de grados $(2,3,3,4,4,5,5)$ posee un ciclo hamiltoniano aunque esta sucesión no satisfaga la condición de Pósa. Haz esto siguiendo estos pasos:
 \begin{enumerate}
  \item Muestra que si $u$ es un vértice de grado tres entonces existe un vértice $v$ de grado cuatro o cinco quqe no es adyacente a $u$.
  \item ¿Qué pasa si agregamos una arista entre $u$ y $v$?
 \end{enumerate}


 \item \textbf{Prueba del teorema de Pósa}
 Mostraremos que si $G$ posee al menos tres vértices, satisface la condición de los grados de Pósa y no es la gráfica completa entonces podemos agregar una arista entre vértices no adyacentes $u$ y $v$ cuyos grados satisfagan que $d(u)+d(v)\geq n$. Repitiendo ésto eventualmente llegaremos a la gráfica completa $K_n$. Se seguirá del teorema del Bondy-Chvátal que $G$ posee un ciclo hamiltoniano.

La clave para probar que existen esos vértices adecuados $u$ y $v$ es fijarse en la sumas $d_i+d_{i+1}$, donde los grados están ordenados en sentido creciente $d_1 \leq d_2 \leq \ldots \leq d_n$.
 \begin{enumerate}
  \item Muestra que si $d_1 + d_2 \geq n$ entonces existen vértices $u$ y $v$ que satisfacen la condición pedida. (Sugerencia: toma un vértice $u$ con grado $d_1$).

Con este resultado, podemos suponer que $d_1 + d_2 < n$ y ahora considerar sumas $d_i + d_{i+1}$ para $i > 2$.

  \item Toma $r$ el mayor entero menor que $n/2$, es decir, $r := n/2 -1$ si $n$ es par o $r:=(n-1)/2$ si $n$ es impar. Muestra que $d_r + d_{r+1} \geq n$.

 Bajo el supuesto de que $d_1 + d_2 < n$, el incicso anterior implica que debe exisitr un $i$ entre $2$ y $r$, inclusive, tal que $d_{i-1}+d_i<n$ y $d_i + d_{i+1}\geq n$.

 \item Con tal $i$, muestra que $d_i < n-i$.
 \item Completa la prueba del teormea de Pósa por medio de mostrar que existen $u$ y $v$ con las condición pedida. (Sugerencia: toma un vértice $u$ con grado $d_i$).
 \end{enumerate}
\end{enumerate}

\begin{teorema}[Teorema de Ore]
 Dada $G$ una gráfica con $n$ vértices, $n \geq 3$, y supón que $G$ satisface que:
\begin{quote}
 \textbf{Condición de adyacencia de Ore} Siempre que $d(u)+d(v)<n$ para cualquier par de vértices $u$ y $v$ entonces son adyacentes.
\end{quote}
Entonces $G$ posee un ciclo hamiltoniano.
\end{teorema}


\subsection*{Extras}
\begin{enumerate}[A.]
 \item \begin{enumerate}
  \item Encuentra una gráfica que tenga sucesión de grados $(3,3,3,3,4,4,4)$ y que no tenga un ciclo hamiltoniano.
  \item Prueba que toda gráfica con la sucesión de arriba debe poseer una trayectoria hamiltoniana. (Sugerencia: añade una arista a la gráfica de forma tla que esta nueva gráfica satisfaga la condición de Pósa. ¿Es esto posible?).
\end{enumerate}
 \item Encuentra un ejemplo de una  gráfica con tres o más vértices regular, conexa, bipartita y sin ciclo hamiltoniano (Sugerencia: piensa en el criterio de la subgráfica).
 \item Prueba el teorema de Ore mediante el uso del teorema de Bondy-Chvátal.
\end{enumerate}
% \item Describe todas las gráficas con $\chi(G)\leq 2$.
% \item ¿Las siguientes ecuaciones son verdaderas?
% \begin{displaymath}
%  \chi(G)=\chi'(L(G))\text{,}\qquad \chi'(G)=\xi(L(G))\text{.}
% \end{displaymath}
% \item Muestra que $\chi'(K_{m,n})=\Delta(K_{m,n})$ exhibiendo una coloración apropiada.
% \item Considera $G$ una gráfica que no sea un ciclo dirigido de longitud impar. Prueba que $\chi'(G)=\Delta(G)$ si todos los ciclos de $G$ tienen la misma paridad.
% \item Prueba que $\chi'(G)=\Delta(G)+1$ para gráficas regulares de orden impar y con al menos una arista.
% \item Una gráfica se dice \emph{isocromática} si $\chi(G)=\chi'(G)$. Encuentra todas las gráficas isocromáticas entre las gráficas completas y las bipartitas.
% \item Encuentra una gráfica cúbica $G$ de orden mínimo con $\chi'(G)=4$.
% \item Diremos que una gráfica $G$ es de \emph{clase 1} si $\chi'(G)=\Delta(G)$ y de \emph{clase 2} si $\chi'(G)=\Delta(G)+1$. Una gráfica es \emph{$\chi'$-crítica} si es conexa, es de clase 2 y al borrar cualquier arista disminuye su índice cromático.
%  \begin{enumerate}
%  \item Construye una gráfica $\chi'$-crítica $G$ de orden cinco con $\Delta(G)=3$.
%  \item ¿Para qué valores de $n$ se tiene que $K_n$ es $\chi'$-crítica?
%  \item Prueba que no existe gráficas $\chi'$-críticas de orden cuatro o seis con $\Delta(G)=3$.
%  \end{enumerate}
% \item Considera una gráfica $G$ con $2n+1$ vértices y más de $n\Delta(G)$ aristas. Entonces $\chi'(G)=\Delta+1$.
% \item Muestra que toda gráfica cúbica hamiltoniana tiene índice cromático tres.
% \item Considera $G:=C[\overline{K_2}]$.
%  \begin{enumerate}
%  \item Si $M$ y $M'$ son dos apareamientos perfectos distintos de $G$, muestra que existe un automorfimo que se lleva a uno en el otro.
%  \item Deduce que $\chi'(G)=4$.
%  \item Más aún, deduce que $G$ no contiene a Petersen.
%  \end{enumerate}
% \end{enumerate}
\end{document}