\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}{Tarea anterior a la décima\\8.10 hrs, 12 de
noviembre de 2009 (Sin prórroga)}

\begin{enumerate}[1.]
 \item ¿Cuáles de las siguientes afirmaciones son ciertas y por qué?
\begin{enumerate}
 \item Si $G$ posee un paseo euleriano cerrado entonces no posee vértices de
corte.
 \item Si $G$ posee un paseo euleriano cerrado entonces no posee puentes
(\textit{i.e.}, aristas de corte).
 \item Si $G$ posee un paseo euleriano cerrado, es de orden impar y
$\overline{G}$ es conexa entonces $\overline{G}$ posee también un paseo
euleriano cerrado.
\end{enumerate}

\item Para que enteros $p \geq q$, $K_{p,q}$ posee un paseo euleriano abierto. 

\item Considera $H$ una subgráfica generadora de una gráfica $G$.  ¿Cuál de las
siguientes afirmaciones es cierta o no y por qué?
\begin{enumerate}
 \item Si $H$ posee un paseo euleriano cerrado entonces $G$ posee un paseo
euleriano cerrado.
 \item Si $H$ posee un paseo euleriano abierto entonces $G$ posee un paseo
euleriano abierto.
 \item Si $H$ posee un ciclo hamiltoniano entonces $G$ posee un ciclo
hamiltoniano.
\end{enumerate}


\item Muestra que si una gráfica satisface la condición de Dirac entonces
también satisface la condición de los grados de Pósa.

\item Prueba que toda gráfica con sucesión de grados $(2$, $3$, $3$, $4$, $4$,
$5$, $5)$ y toda gráfica con sucesión de grados $(4$, $5$, $5$, $5$, $5$, $6$,
$6$, $6$, $6$, $6$, $6)$ contienen un ciclo hamiltoniano, pese a que no
satisfacen la condición de los grados de Pósa. 

\item Supón que agregamos una arista a $G$ que no tenía antes, uniendo dos
vértices $u$ y $v$ no adyacentes en $G$ y que la gráfica con la nueva arista
posee un ciclo hamiltoniano.  Entonces ¿qué existe necesariamente en $G$?

\item \begin{enumerate}
       \item Encuentra una gráfica con sucesión de grados $(3$, $3$, $3$, $3$,
$4$, $4$, $4)$ que no tiene un ciclo hamiltoniano.
       \item Prueba que toda gráfica con la sucesión de grados previa debe
poseer una trayectoria hamiltoniana.
      \end{enumerate}

\item Encuentra un ejemplo de una gráfica con tres o más vértices que sea
regular, conexa, bipartita y que no posea ciclos hamiltonianos.

\begin{teorema}[Teorema de Ore]
Dada $G$ una gráfica con $n$ vértices, donde $n \geq 3$, que satisface la
condición de adyacencia de Ore, a saber, siempre que $d(u)+d(v) <n$ para
cualesquiera dos vértices $u$ y $v$ entonces $u$ y $v$ son adyacentes.  Entonces
$G$ posee un ciclo hamiltoniano.
\end{teorema}

\item Prueba con el Teorema de Bondy-Chvátal el Teorema de Ore.

\item Encuentra una gráfica que satisfaga la condición de los grados de Pósa
pero no la condición de adyacencia de Ore.

\item Considera $G$ una gráfica con un paseo euleriano abierto y con un ciclo
hamiltoniano, llamemos a este último $C$.  Supón que $v(G)=12$, $e(G)=17$,
$\delta(G)=2$ y $\Delta(G)=4$.
\begin{enumerate}
 \item ¿Cuántos vértices de grado tres puede tener $G$?
 \item ¿Cuántos vértices de grado dos tiene $G$?
 \item Construye una gráfica que satisfaga lo anterior.
 \item Supón que todos los vértices de grado impar son adyacentes en $G$, pero
que ninguno de los vértices de grado dos son adyacentes entre sí.  ¿Qué puedes
decir sobre la estructura de la subgráfica inducida por el conjunto de vértices
de grado cuatro en $G$? 
\end{enumerate}

\item Considera una gráfica $G$ con un paseo euleriano abierto y que posee
posee $C$ un ciclo hamiltoniano.  Supón que $v(G)=7$, $e(G)=12$, $\delta(G)=2$,
$\Delta(G)=5$ y que $G$ posee exactamente dos vértices de grado dos.
\begin{enumerate}
 \item Encuentra el número de vértices de grado cuatro y el número de vértices
de grado cinco en $G$.
 \item Supón que los dos vértices de grado dos son adyacentes en $C$. 
Construye todas las posibles gráficas que lo satisfagan.
\end{enumerate}

\item Prueba que $\alpha(G) \leq \frac{v(G)}{2}$ para cualquier gráfica $G$ que posea un ciclo hamiltoniano.
\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.
\begin{enumerate}
 \item Determina el máximo valor posible para $\Delta(G)$ y construye todas las
gráficas que lo alcancen.
 \item Supón que $\Delta(G)=:4$
\begin{enumerate}
 \item Determina el número de vértices de grado cuatro en $G$.
 \item Supón que ninguno de los vértices de grado cuatro son adyacentes. 
Construye\hyphenation{Cons-tru-ye} todas las posibles gráficas que satisfagan lo
anterior.
\end{enumerate}
\end{enumerate}

\item Dado un tablero de ajedrez (de ocho por ocho), asociémosle una gráfica de
la siguiente\hyphenation{si-guien-te} manera: por cada cuadro pongamos un
vértice y dos vértices son adyacentes si y sólo si sus cuadros correspondientes
son adyacentes vertical u horizontalmente en el tablero.  Dado cualquier
cuadrícula de $m \times n$ podemos asociarle una gráfica.  Prueba que tales
gráficas poseen un ciclo hamiltoniano si y sólo si $m$ o $n$ es par.
\end{enumerate}

\end{document}