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

\begin{document}
\header{Teoría de las Gráficas}{Segunda tarea\\14 de setiembre de 2010}

\begin{enumerate}[1.]
 \item Considera $X$ y $Y$ conjuntos finitos.  Prueba que: \begin{enumerate}
 \item $\lvert X \cup Y \rvert +\lvert X \cap Y \rvert = \lvert X \rvert + \lvert Y \rvert$ y
 \item $\lvert X \cup Y \rvert^2 +\lvert X \cap Y \rvert^2 \geq \lvert X \rvert^2 + \lvert Y \rvert^2$
\end{enumerate}

\item Muestra que toda gráfica de orden $n$ es isomorfa a una subgráfica de la gráfica completa con $n$ vértices.

\item Muestra que dos gráficas son isomorfas si y sólo si sus completementos son isomorfos.

\item Encuentra dos gráficas no isomorfas cuya sucesión de grados sea $(1$, $1$, $2$, $2$, $3$, $3)$.

\item Si $G$ y $G'$ son dos gráficas isomorfas entonces tienen la misma sucesión de grados.

\item Muestra que no existe una gráfica simple de orden doce y tamaño veintiocho en la que (i) el grado de cada vértice sea tres o cuatro y (ii) el grado de cada vértice sea tres o seis.

\item ¿$(2$, $3$, $3$, $3$, $3$, $3$, $4$, $5)$ es una sucesión de grados? De ser así, dibuja la gráfica.

\item ¿$(1$, $3$, $3$, $4$, $5$, $6$, $6)$ es una sucesión de grados? De ser así, dibuja la gráfica.

\item Muestra que existe una gráfica simple con siete vértices y doce aristas tal que el grado de cada vértice es dos, tres o cuatro.


\item Considera $G[X$, $Y]$ una gráfica bipartita, con $\lvert X \rvert = r$ y $\lvert Y \rvert = s$.   Muestra que $e(G) \leq rs$ (donde $X$ y $Y$ denotan las partes de la partición, así toda arista tiene extremos en ambos conjuntos y $e(G)$ denota el número de aristas de $G$).


\end{enumerate}


\subsubsection*{Extras}
\begin{enumerate}[A.]
 \item Supón que $G$ es una gráfica $k$-regular de orden $n$ y tamaño $m$, con $k \geq 0$, $m \geq 0$ y $n \geq 1$.  Encuentra una relación entre $k$, $n$ y $m$.  Justifica tu respuesta.
\item Considera $G$ una gráfica de orden $n$ tal que para ninguna terna de vértices $u$, $v$, $w$ se tiene que $uv$, $vw$, $wu$ son todas aristas de $G$ (lo anterior es equivalente a decir que $G$ es \emph{$K_3$-libre}, es decir, que $G$ no posee a $K_3$ como subgráfica).  Muestra que
\begin{displaymath}
 n \geq \delta(G)+ \Delta(G)\text{.}
\end{displaymath}
\end{enumerate}
% 
% \begin{figure}[!h]
% 	\begin{minipage}[b]{0.5\linewidth}
% 	\centering
% 	\begin{displaymath}
% 	\xygraph{
% 	!{<0cm,0cm>;<2cm,0cm>:<0cm,2cm>::}
% 	!{(0,0.55) }*{\bullet}="2"
% % 	!{(-0.2,0.55) }*{v_2}
% 	!{(0.6,1) }*{\bullet}="1"
% % 	!{(0.6,1.2) }*{v_1}
% 	!{(0.3,-0.1) }*{\bullet}="3"
% % 	!{(0.3,-0.3) }*{v_3}
% 	!{(0.9,-0.1) }*{\bullet}="4"
% 	!{(0.9,0.8) }*{\bullet}="6"
% 	!{(1.1,1) }*{\bullet}="6b"
% 	!{(1.3,1.2) }*{\bullet}="7"
% % 	!{(0.9,-0.3) }*{v_4}
% 	!{(1.2,0.55) }*{\bullet}="5"
% 	!{(1.3,-0.5) }*{\bullet}="8"
% % 	!{(1.4,0.55) }*{v_5}
% 	"1"-"2" "1"-"6" "5"-"6" "2"-"3"
% 	"3"-"4" "5"-"4" "5"-"2" "6b"-"7" "4"-"8" "6b"-"6"
% 	}
% 	\end{displaymath}
% 	\caption{$G_1$}
% 	\label{fig:g1}
% 	\end{minipage}
% 	\hspace{0.25cm}	
% 	\begin{minipage}[b]{0.5\linewidth}
% 	\centering
% 	\begin{displaymath}
% 	\xygraph{
% 	!{<0cm,0cm>;<2cm,0cm>:<0cm,2cm>::}
% 	!{(0,0.55) }*{\bullet}="2"
% % 	!{(-0.2,0.55) }*{v_2}
% 	!{(0.6,1) }*{\bullet}="1"
% % 	!{(0.6,1.2) }*{v_1}
% 	!{(0.3,-0.1) }*{\bullet}="3"
% % 	!{(0.3,-0.3) }*{v_3}
% 	!{(0.9,-0.1) }*{\bullet}="4"
% 	!{(0.3,0.8) }*{\bullet}="6"
% 	!{(0.1,1) }*{\bullet}="6b"
% 	!{(-0.1,1.2) }*{\bullet}="7"
% % 	!{(0.9,-0.3) }*{v_4}
% 	!{(1.2,0.55) }*{\bullet}="5"
% 	!{(1.3,-0.5) }*{\bullet}="8"
% % 	!{(1.4,0.55) }*{v_5}
% 	"1"-"6" "2"-"6" "2"-"3" "4"-"5"
% 	"3"-"4" "5"-"1" "5"-"2" "6b"-"7" "4"-"8" "6b"-"6"
% 	}
% 	\end{displaymath}
% 	\caption{$G_2$}
% 	\label{fig:g2}
% 	\end{minipage}
% \end{figure}

\end{document}