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

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas\hyphenation{res-pues-tas}. La tarea se puede entregar en equipos de hasta dos personas.
\paragraph{ }
Recuerden que las definiciones son las importantes. Para probar algo no siempre es bueno sobreargumentar (ni tampoco quedar falto de argumentos). Los mejores argumentos suelen ser los simples.
\paragraph{}
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 ajenos) de $W$.  Un
\emph{sistema de distintos representantes (SDR)} para la familia $(S_1$, $S_2$,
\ldots, $S_n$) es una $n$-ada $(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$.



\begin{enumerate}[1.]
\item \begin{enumerate} 
       \item Considera el conjunto de los números naturales
$\mathbb{N}$ y la siguiente familia de subconjuntos de $\mathbb{N}$:
\begin{displaymath}
 S_1=\{1,4\}, \, S_2=\{2,5\}, \, S_3=\{ 4 \}, S_4=\{3,5\} \text{ y }
S_5=\{3,5\}\text{.}
\end{displaymath}
¿Posee la familia $(S_1$, $S_2$, \ldots, $S_5)$ un sistema de distintos
representantes? ¿Por qué?
       \item Considera el conjunto de los números naturales
$\mathbb{N}$ y la siguiente familia de subconjuntos de $\mathbb{N}$:
\begin{displaymath}
 S_1=\{1\}, \, S_2=\{2,3\}, \, S_3=\{ 1,4,5 \}, S_4=\{ 1,2\} \text{ y }
S_5=\{1,3\}\text{.}
\end{displaymath}
¿Posee la familia $(S_1$, $S_2$, \ldots, $S_5)$ un sistema de distintos
representantes? ¿Por qué?
      \end{enumerate}

En general, dada una familia de conjuntos $(S_1$, $S_2$, \ldots, $S_n)$, si
existen $k$ de ellos cuya unión tiene menos de $k$ elementos entonces la
familia no posee un sistema de representantes distintos.

\item Ésto es, si existe algún $I \subseteq \{1$, $2$, \ldots, $n\}$ tal que:
\begin{displaymath}
 \Big\lvert \bigcup_{i\in I} S_i \Big\rvert \qquad \lvert I \lvert\text{,}
\end{displaymath}

\item Enuncia el recíproco de la afirmación anterior.

\item Representa la situación del primer problema en forma de un gráfica. 
(\textit{Sugerencia.} Recuerda que la \emph{pertenencia} es una relación sobre
la clase de los conjuntos).

\item Con el Teorema de Hall, prueba que:

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

\item Prueba que si tanto $M$ como $M^*$ son apareamientos en una gráfica $G$ entonces $M \vartriangle M^*$ es un apareamiento de $G$.

\item Considera una gráfica bipartita $G[X$, $Y]$.  Para algún $S \subseteq X$,
llama $E_1$ al conjunto de las aristas en $G$ incidentes con algún vértice en
$S$ y llama $E_2$ al conjunto de las aristas de $G$ incidentes con algún
vértice en $N(S)$.  ¿Es cierto, en general, que $E_1 \subseteq E_2$? ¿Por qué?


\item \begin{enumerate}
       \item Considera $G$ una gráfica bipartita.  Prueba que $G$ posee un
apareamiento perfecto si y sólo si $\lvert S \rvert \leq \lvert N(S) \rvert$.
\begin{sloppypar}
       \item Da un ejemplo que la condición anterior no garantiza la existencia de un apareamiento perfecto en gráficas arbitrarias.
\end{sloppypar}
      \end{enumerate}

\item Considera una gráfica bipartita $G[X$, $Y]$ tal que todo vértice de $X$ es de grado impar.  Supón que cualesquiera dos vértices de $X$ tienen un número par de vecinos en común.  Muestra que $G$ posee un apareamiento que satura $X$.

\item Dados $G[X$, $Y]$ una gráfica bipartita y $S_1$ y $S_2$ subconjuntos de $X$, muestra que:
\begin{displaymath}
\lvert N(S_1) \rvert + \lvert N(S_2)\rvert \geq \lvert N(S_1 \cup S_2)\lvert + \lvert N(S_1 \cap S_2)\rvert\text{.}
\end{displaymath}
\end{enumerate}

\subsubsection*{Extras}
\begin{enumerate}[A.]
\item \begin{enumerate}
       \item Muestra que la gráfica de Petersen tiene exactamente seis apareamientos perfectos.
       \item Llamemos $pm(G)$ al número de apareamientos perfectos en una gráfica $G$.  Calcula $pm(K_{2n})$ y $pm(K_{n,n})$.
      \end{enumerate}

\item Muestra que toda gráfica $2$-conexa que posee un apareamiento perfecto posee al menos dos apareamientos perfectos.

Recuerda que dados dos conjuntos $S$ y $T$,  la \emph{diferencia simétrica} de $S$ y $T$, $S\vartriangle T$, es $(S \setminus T) \cup (T \setminus S)$, lo que es igual a $(S \cup T)\setminus (S \cap T)$.

\item Considera $S$ y $T$ subconjuntos independientes máximos de vértices de una gráfica $G$.  Muestra que $G[S \vartriangle T ]$ posee un apareamiento perfecto.
\end{enumerate}

\end{document}