\documentclass[letterpaper, 12pt]{article}
  \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{Gráficas y juegos}{Cuarta tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas.

\begin{enumerate}
 \item Prueba que si una gráfica posee una partición de sus aristas en ciclos entonces posee un paseo euleriano cerrado.
 \item Prueba el teorema de Ore 2: dada una gráfica $G$, si para cualquier par de vértices no adyacentes $u$ y $v$ se satisface que
\begin{displaymath}
 \delta(u)+\delta(v) \geq p
\end{displaymath}
entonces $G$ es posee un ciclo hamiltoniano.

 \item Prueba que si $G$ satisface la condición de Ore dos y $u$, $v$ son vértices no adyacentes de $G$ entonces $G+uv$ satisface la condición de Ore 2.

 \item Muestra que los recíprocos de los teorema de Ore uno y dos son falsos.
 
 \item Prueba que si una gráfica posee un ciclo hamiltoniano entonces no tiene vértices de corte.
 
 \item Prueba que si una gráfica tiene $2n$ vértices de grado impar entonces existe una partición de las aristas de $G$ en $n$ paseos abiertos.
 
 \item Prueba o da un contraejemplo de las siguientes afirmaciones:
\begin{enumerate}
\item Toda gráfica euleriana es hamiltoniana.
\item Toda gráfica hamiltoniana es euleriana.
\end{enumerate}

 \item Completa la prueba del lema de Berge: prueba que si $M$ es un apareamiento y $P$ una trayectoria $M$-aumentante entonces $(M-P) \cup (P-M)$ es un apareamiento.

 \item Completa la prueba del teorema de Hall: prueba que si $G$ es una gráfica con bipartición $(X$, $Y)$, $M$ un apareamiento en $G$, $x_0 \in X$ tal que $x_0$ no está $M$-saturado, $S=\{z \in X : \text{ existe una } x_0z \text{-trayectoria }M\text{-alternante}\}$ y $T=\{z \in Y : \text{ existe una } x_0z \text{-trayectoria }M\text{-alternante}\}$ entonces todo punto de $S \setminus \{x_0\}$ está apareado bajo $M$ con uno de $T$.
 
 \item Considera $W$ un conjunto no-vacío y $S_1$, $S_2$, \ldots, $S_n$ una familia
finita y no-vacía de subconjuntos (no necesariamente distintos) de $W$.  Un
\emph{sistema de distintos representantes (SDR)} para la familia $(S_1$, $S_2$,
\ldots, $S_n$) es una $n$-eada $(a_1$, $a_2$, \ldots $a_n)$ tal que $a_i \in
S_i$ para cada $i=1$, $2$, \ldots, $n$, y $a_i \neq a_j$ si y sólo si $i \neq
j$.

Prueba el siguiente teorema:

\begin{teorema}
 La familia $(S_1$, $S_2$, \ldots, $S_n)$ de subconjuntos finitos no-vacíos de
un conjunto $W$ posee un sistema de representantes distintos si y sólo si
\begin{displaymath}
 \Big\lvert \bigcup_{i\in I} S_i \Big\rvert \geq \lvert I \lvert\text{,}
\end{displaymath}
para todos los subconjuntos $I$ de $\{1$, $2$, \ldots, $n\}$.
\end{teorema}
 (\emph{Sugerencia.} Usa el teorema de Hall.)
\end{enumerate}

\section*{Extras}

\begin{enumerate}[A.]
 \item Da un ejemplo de una gráfica, con al menos tres vértices, bipartita, regular y conexa pero que no sea posea un ciclo hamiltoniano.
  \item Prueba que si $G$ es bipartita y posee un ciclo hamiltoniano entonces sus partes tienen la misma cardinalidad.
\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 de esta manera.  Prueba que tales
gráficas poseen un ciclo hamiltoniano si y sólo si $m$ o $n$ es par.
 \item Muestra que si $G$ es una gráfica $2$-conexa que posee un apareamiento perfecto posee al menos dos apareamientos perfectos.
 \item Prueba que un árbol posee a lo más un apareamiento perfecto.
 

\end{enumerate}

 


% \section*{Extras}
% \begin{enumerate}[A.]
% 
%  \item ¿Las siguientes tres gráficas son o no isomorfas? Argumenta porqué no o prueba porqué sí.
% \definecolor{qqqqff}{rgb}{0.49,0.49,1}
% \definecolor{qqqqff}{rgb}{0,0,1}
% \begin{figure}[!h]
% \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.75cm,y=0.75cm]
% % \clip(-1.32,-4.04) rectangle (18.18,6.3);
% \draw (0.48,2.52)-- (2.44,4.18);
% \draw (2.44,4.18)-- (4.52,2.5);
% \draw (4.52,2.5)-- (3.76,0);
% \draw (3.76,0)-- (1.36,0);
% \draw (1.36,0)-- (0.48,2.52);
% \draw (1.64,2.1)-- (3.22,2.1);
% \draw (3.22,2.1)-- (2,1);
% \draw (2.44,2.88)-- (2,1);
% \draw (2.44,2.88)-- (3,1);
% \draw (3,1)-- (1.64,2.1);
% \draw (2.44,4.18)-- (2.44,2.88);
% \draw (1.64,2.1)-- (0.48,2.52);
% \draw (2,1)-- (1.36,0);
% \draw (3,1)-- (3.76,0);
% \draw (3.22,2.1)-- (4.52,2.5);
% \draw(8.5,1.66) circle (1.6cm);
% \draw (8.5,3.79)-- (8.5,1.66);
% \draw (8.5,1.66)-- (6.66,0.59);
% \draw (10.09,3.08)-- (7.62,-0.28);
% \draw (8.5,1.66)-- (10.34,0.59);
% \draw (6.91,3.08)-- (9.48,-0.23);
% \draw (6.4,2)-- (10.6,2.02);
% \draw (14.42,2.6)-- (14.48,1.66);
% \draw (14.48,1.66)-- (13.84,1.22);
% \draw (14.48,1.66)-- (15.2,1.26);
% \draw (12.38,1.48)-- (14.42,2.6);
% \draw (14.42,2.6)-- (16.56,1.5);
% \draw (13.44,3.76)-- (15.7,3.74);
% \draw (15.7,3.74)-- (16.56,1.5);
% \draw (16.56,1.5)-- (15.62,-0.14);
% \draw (15.62,-0.14)-- (13.54,-0.14);
% \draw (13.54,-0.14)-- (12.38,1.48);
% \draw (13.44,3.76)-- (12.38,1.48);
% \draw (13.44,3.76)-- (13.84,1.22);
% \draw (15.2,1.26)-- (15.7,3.74);
% \draw (13.84,1.22)-- (15.62,-0.14);
% \draw (15.2,1.26)-- (13.54,-0.14);
% \fill [color=qqqqff] (2,1) circle (1.5pt);
% \fill [color=qqqqff] (1.64,2.1) circle (1.5pt);
% \fill [color=qqqqff] (2.44,2.88) circle (1.5pt);
% \fill [color=qqqqff] (3,1) circle (1.5pt);
% \fill [color=qqqqff] (3.22,2.1) circle (1.5pt);
% \fill [color=qqqqff] (1.36,0) circle (1.5pt);
% \fill [color=qqqqff] (3.76,0) circle (1.5pt);
% \fill [color=qqqqff] (4.52,2.5) circle (1.5pt);
% \fill [color=qqqqff] (0.48,2.52) circle (1.5pt);
% \fill [color=qqqqff] (2.44,4.18) circle (1.5pt);
% \fill [color=qqqqff] (8.5,1.66) circle (1.5pt);
% \fill [color=qqqqff] (7.62,-0.28) circle (1.5pt);
% \fill [color=qqqqff] (9.48,-0.23) circle (1.5pt);
% \fill [color=qqqqff] (6.66,0.59) circle (1.5pt);
% \fill [color=qqqqff] (10.34,0.59) circle (1.5pt);
% \fill [color=qqqqff] (6.4,2) circle (1.5pt);
% \fill [color=qqqqff] (10.6,2.02) circle (1.5pt);
% \fill [color=qqqqff] (6.91,3.08) circle (1.5pt);
% \fill [color=qqqqff] (10.09,3.08) circle (1.5pt);
% \fill [color=qqqqff] (8.5,3.79) circle (1.5pt);
% \fill [color=qqqqff] (14.48,1.66) circle (1.5pt);
% \fill [color=qqqqff] (14.42,2.6) circle (1.5pt);
% \fill [color=qqqqff] (13.84,1.22) circle (1.5pt);
% \fill [color=qqqqff] (15.2,1.26) circle (1.5pt);
% \fill [color=qqqqff] (12.38,1.48) circle (1.5pt);
% \fill [color=qqqqff] (16.56,1.5) circle (1.5pt);
% \fill [color=qqqqff] (13.54,-0.14) circle (1.5pt);
% \fill [color=qqqqff] (15.62,-0.14) circle (1.5pt);
% \fill [color=qqqqff] (13.44,3.76) circle (1.5pt);
% \fill [color=qqqqff] (15.7,3.74) circle (1.5pt);
% \end{tikzpicture}
% \end{figure}
% 
% \item Muestra que la siguiente gráfica es autocomplementaria:
% \begin{figure}[!h]
% \definecolor{qqqqff}{rgb}{0,0,1}
% \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
% % \clip(-4.3,-4.04) rectangle (15.2,6.3);
% \draw (4,4)-- (5,4);
% \draw (5,4)-- (6,3);
% \draw (6,3)-- (6,2);
% \draw (6,2)-- (5,1);
% \draw (5,1)-- (4,1);
% \draw (4,1)-- (3,2);
% \draw (3,2)-- (3,3);
% \draw (3,3)-- (4,4);
% \draw (3,3)-- (4,1);
% \draw (4,1)-- (6,2);
% \draw (6,2)-- (5,4);
% \draw (5,4)-- (3,3);
% \draw (4,4)-- (5,1);
% \draw (3,2)-- (6,3);
% \fill [color=qqqqff] (3,3) circle (1.5pt);
% \fill [color=qqqqff] (3,2) circle (1.5pt);
% \fill [color=qqqqff] (4,1) circle (1.5pt);
% \fill [color=qqqqff] (5,1) circle (1.5pt);
% \fill [color=qqqqff] (6,2) circle (1.5pt);
% \fill [color=qqqqff] (6,3) circle (1.5pt);
% \fill [color=qqqqff] (4,4) circle (1.5pt);
% \fill [color=qqqqff] (5,4) circle (1.5pt);
% \end{tikzpicture}
% \end{figure}
% 
%  \item Muestra dos gráficas, con seis vértices, tal que todos sus vértices tengan grado dos pero que no sean isomorfas entre sí.
% 
%  \item Muestra que si $G$ es autocomplementaria entonces su orden es múltiplo de cuatro o múltiplo de cuatro más uno.
% \end{enumerate}

\end{document}
