\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\\3 de setiembre de 2009}

\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 \begin{itemize}
       \item Prueba que una gráfica $G$ es completa si y sólo si $e(G)=\binom{v(G)}{2}$.
       \item Completa la prueba (vista en clase) de que
\begin{displaymath}
\sum_{v \in V(G)} d(v) = 2e(G)\text{.}
\end{displaymath}

      \end{itemize}

% \item Para cualesquiera enteros no-negativos $a$ y $b$ tales que $a \leq b$ construye una gráfica $G$ con $\delta(G)=a$ y $\Delta(G)=b$.

\item Considera $G$ una gráfica de orden ocho y tamaño 15 en la cual cada vértice es de grado 3 ó 5.  ¿Cuántos vértices de grado cinco tiene $G$?  Dibuja una.

\item Considera $H$ una gráfica de orden diez tal que para todo vértice $v$ de $H$, $3 \leq d(v) \leq 5$.  No todo vértice es par.  No posee dos vértices de grado impar con el mismo grado.  ¿Cuál es el tamaño de $H$?

\item Considera $G$ una gráfica de orden 14 y tamaño 30 en la cual todo vértice es de grado cuatro o cinco.  ¿Cuántos vértices de grado cinco posee G?  Dibuja una.

\item Dibuja todas las gráficas regulares de orden $n$, con $n = 2$, \ldots, $6$.

\item \begin{itemize}
       \item ¿Existirá una gráfica $G$ de orden cinco tal que $\delta(G)=1$ y $\Delta(G)=4$?
       \item ¿Existirá una gráfica $G$ de orden cinco tal que posee dos vértices de grado cuatro y $\delta(G)=1$?
      \end{itemize}

\item ¿Existirá una gráfica $3$-regular con ocho vértices?  ¿Y una $3$-regular con nueve?

\item Construye una gráfica $3$-regular de orden doce.  ¿Cuál es su tamaño?  ¿Existirá una de orden once?  ¿Por qué?

\item Considera $H$ una gráfica $k$-regular de orden $n$.  Si $e(H)=10$, encuentra todos los posible valores para $k$ y $n$; y para cada caso, construye una gráfica que los satisfaga.

\item Encuentra todos los enteros $n$ tales que $100 \leq e(K_n) \leq 200$.

\item Considera $G[X$, $Y]$ una gráfica bipartita, con $\lvert X \rvert = r$ y $\lvert Y \rvert = s$.
\begin{enumerate}[a)]
 \item Muestra que $e(G) \leq rs$.
 \item Deduce que $e(G) \leq n^2/4$.
 \item Describe las gráficas bipartitas $G$ para las cuales la igualdad se tiene en (b).
\end{enumerate}

\item Prueba que si $G$ es disconexa entonces $\overline{G}$ es conexa.  ¿El recíproco es cierto?

\end{enumerate}


\subsubsection*{Extras}
\begin{enumerate}[A.]
 \item Considera $H$ una gráfica de orden ocho y tamaño 13 con $\delta(H) =2$ y $\Delta (H)=4$  Denota por $n_i$ el número de vértices en $H$ de grado $i$, donde $i=2$, $3$, $4$.  Supón que $n_3 \geq 1$.  Encuentra todas las posibles soluciones para $(n_2$, $n_3$, $n_4)$.  Para cada una de tus respuestas, construye una gráfica que los satisfaga.
 \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 Prueba que si $G$ es autocomplementaria (es decir, $G \cong \overline{G}$) entonces
\begin{displaymath}
 v(G) \equiv 0\text{, }1 \pmod 4
\end{displaymath}
\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}
\item Toma $n \geq 2$ puntos en el plano tal que la distancia entre cualesquiera dos de esos puntos es al menos uno.  Prueba que existen a lo más $3n$ pares de esos vértices a distancia exactamente uno.


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