\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}{Gráfica}

\begin{document}
\header{Teoría de las Gráficas}{Nona tarea\\5 de junio de 2009}

Un subconjunto de vértices de una gráfica $G$ se dice \emph{independiente} si dos a dos los vértices no son adyacentes (i.e., la gráfica inducida por el subconjunto no tiene aristas).  A un subconjunto de vértices independente de cardinalidad máxima se le llama un \emph{subconjunto de vértices independiente máximo}.  A la cardinalidad de los subconjuntos de vértices independientes máximos se le suele llamar el \emph{número de independencia de $G$} y se le denota por $\beta(G)$.


\begin{teorema}[Tutte, 1947]
 Una gráfica $G$ tiene un apareamiento perfecto si y sólo si el número de componentes de orden impar de $G-S$ es menor o igual que la cardinalidad de $S$, para cualquier subconjunto $S \subseteq V(G)$.
\end{teorema}


\begin{enumerate}[1.]
 \item Considera $M$ un apareamiento y $P$ una trayectoria $M$-aumentable.  Muestra que
\begin{displaymath}
M' := M \bigtriangleup A(P) = (M \setminus A(P)) \cup (A(P) \setminus M) = (M \cup A(P))\setminus (M \cap A(P))
\end{displaymath}
es un apareamiento y $\lvert M' > \geq \lvert M \rvert$.

 \item Encuentra todos los apareamientos perfectos en las gráficas de las Gráficas~\ref{fig:ej1a} y~\ref{fig:ej1b}.
 \item Da un ejemplo de una gráfica cúbica (i.e., $3$-regular) que no tenga apareamientos perfectos.
 \item Prueba o da un contraejemplo: si $G$ tiene un apareamiento perfecto entonces $\overline{G}$ tiene un apareamiento perfecto.
 \item Muestra que un árbol tiene a lo más un apareamiento perfecto.
 \item Caracteriza los árboles con un apareamiento perfecto (sin usar el Teorema de Tutte).
 \item ¿Qué cardinalidad tiene un apareamiento perfecto?  Si un apareamiento tiene esa cardinalidad ¿entonces es perfecto?  Pruébalo.
 \item Demuestra que una gráfica $G$ es bipartita si y sólo si para toda subgráfica $H$ de $G$ se tiene que:
\begin{displaymath}
\beta(H) \geq \frac{1}{2}\lvert V(H)\rvert\text{.}
\end{displaymath}
 \item (Petersen, 1891) Prueba que una gráfica cúbica sin puentes tiene un apareamiento perfecto.
 \item Considera un conjunto finito $A$ de conjuntos finitos $A_1$, \ldots, $A_n$.  $A$ posee un \emph{sistema de representates} si y sólo existe $\{a_1$, \ldots, $a_n\}$ tal que $a_i \in A_i$.  Muestra que $A$ posee un sistema de representantes si y sólo si
\begin{displaymath}
 \bigg\lvert \bigcup_{i\in I} A_i \bigg\rvert \geq \lvert I \rvert
\end{displaymath}
para todo $I \subseteq \{1$, \ldots, $n\}$.


\end{enumerate}
\begin{figure}[!h]
	\begin{displaymath}
	\xygraph{
	!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
	!{(0,1) }*{\bullet}="1"
	!{(0,1.4) }*{a}
	!{(1,1) }*{\bullet}="2"
	!{(1,1.4) }*{b}
	!{(2,1) }*{\bullet}="3"
	!{(2,1.4) }*{c}
	!{(3,1) }*{\bullet}="4"
	!{(3,1.4) }*{d}
	!{(0,0) }*{\bullet}="5"
	!{(0,-0.4) }*{e}
	!{(1,0) }*{\bullet}="6"
	!{(1,-0.4) }*{f}
	!{(2,0) }*{\bullet}="7"
	!{(2,-0.4) }*{g}
	!{(3,0) }*{\bullet}="8"
	!{(3,-0.4) }*{h}
	"1"-"2" "2"-"3" "3"-"4" "1"-"5" "2"-"6"
	"3"-"7" "4"-"8" "5"-"6" "7"-"8"
	}
	\end{displaymath}
	\caption{Ejercicio~1}
	\label{fig:ej1a}
\end{figure}
\begin{figure}[!h]
	\begin{displaymath}
	\xygraph{
	!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
	!{(0,1) }*{\bullet}="1"
	!{(0,1.4) }*{a}
	!{(1,1) }*{\bullet}="2"
	!{(1,1.4) }*{b}
	!{(2,1) }*{\bullet}="3"
	!{(2,1.4) }*{c}
	!{(3,1) }*{\bullet}="4"
	!{(3,1.4) }*{d}
	!{(0,0) }*{\bullet}="5"
	!{(0,-0.4) }*{e}
	!{(1,0) }*{\bullet}="6"
	!{(1,-0.4) }*{f}
	!{(2,0) }*{\bullet}="7"
	!{(2,-0.4) }*{g}
	!{(3,0) }*{\bullet}="8"
	!{(3,-0.4) }*{h}
	"1"-"5" "1"-"6" "2"-"5" "2"-"7" "2"-"3"
	"3"-"6" "3"-"8" "4"-"7" "4"-"8" "6"-"7"
	}
	\end{displaymath}
	\caption{Ejercicio~1}
	\label{fig:ej1b}
\end{figure}

\begin{enumerate}[A.]
 \item[Extra.] Prueba que una gráfica cúbica con a lo más dos puentes posee un apareamiento perfecto.
\end{enumerate}

\end{document}