\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}{Primera tarea\\27 de agosto de 2009}

\begin{enumerate}[1.]
\item Define una gráfica $G$ tal que $V(G)=\{2$, $3$, $4$, $5$, $11$, $12$, $13$, $14\}$ y dos vértices $u$ y $v$ son adyacentes si y sólo si $\mcd(u$, $v)=1$.  Dibújala y determina $e(G)$.

\item Considera $G$ una gráfica con $V(G)=\{1$, $2$, \ldots, $10\}$, tal que dos números $i$ y $j$ en $V(G)$ son adyacentes si y sólo si $\lvert i - j \rvert \leq 3$.  Dibuja la gráfica $G$ y determina $e(G)$.

\item Considera $G$ una gráfica con $V(G)=\{1$, $2$, \ldots, $10\}$, tal que dos números $i$ y $j$ en $V(G)$ son adyacentes si y sólo si $i+j$ es múltiplo de cuatro.  Dibuja la gráfica $G$ y determina $e(G)$.

\item Considera $G$ una gráfica con $V(G)=\{1$, $2$, \ldots, $10\}$, tal que dos números $i$ y $j$ en $V(G)$ son adyacentes si y sólo si $i\cdot j$ es múltiplo de diez.  Dibuja la gráfica $G$ y determina $e(G)$.

\item Encuentra la matriz de adyacencia y la matriz de incidencia de la siguiente gráfica $G$ (Figura~\ref{fig:G}).
\begin{figure}[!h]
	\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.3) }*{v_4}
	!{(1.2,0.55) }*{\bullet}="5"
	!{(1.4,0.55) }*{v_5}
	"1"-"2" "1"-"3" "1"-"4" "1"-"5" "2"-"3"
	"3"-"4" "5"-"4"
	}
	\end{displaymath}
	\caption{$G$}
	\label{fig:G}
\end{figure}

\item $\mathbf{X}$ es la matriz de adyacencia de la gráfica $G$.  Dibújala.

\begin{displaymath}
\mathbf{X} =
\left( \begin{array}{ccccc}
0 & 1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 \\
\end{array} \right)
\end{displaymath}

\item El número
\begin{displaymath}
d(G):=\frac{1}{v(G)}\sum_{v\in V(G)} d(v)
\end{displaymath}
es el \emph{grado promedio} de $G$.  Muestra \textbf{con todo detalle} que
\begin{displaymath}
\delta(G) \leq d(G) \leq \Delta(G)\text{.}
\end{displaymath}

\item \begin{enumerate} \item Prueba con detalle que toda en toda gráfica $G$ existen al menos dos vértices que poseen el mismo grado.
\item Muestra que, en cualquier grupo de dos o más personas, siempre existen dos personas que poseen el mismo número de amigos dentro del grupo.
\item Describe un grupo de cinco personas, en el cual cualesquiera dos de sus miembros tienen exactamente un amigo en común.  ¿Puedes encontrar un grupo de cuatro personas con la misma propiedad?
\end{enumerate}

\item Dibuja las once gráficas no isomórficas con cuatro vértices.

\item Dada una gráfica $G$, se define el \emph{complemento} de $G$ (denotado como $\overline{G}$) como la gráfica con:
\begin{compactitem}
\item $V(G)=V(\overline{G})$ y
\item $(u$, $v) \in E(\overline{G})$ si y sólo $(u$, $v) \notin E(G)$ (siempre que $u \neq v$).
\end{compactitem}
\begin{compactenum}
\item Muestra que $\overline{G}$ es también una gráfica.
\item Si $H \leq G$ ¿entonces $\overline{H} \leq \overline{G}$?
\item Una gráfica es \emph{autocomplementaria} si $G\cong \overline{G}$.  Dibuja todas las gráficas autocomplementarias de orden menor o igual que cinco.
\end{compactenum}

\end{enumerate}

\begin{enumerate}
 \item [Extra.]  Prueba que $G_1$ y $G_2$ (Figuras~\ref{fig:g1} y \ref{fig:g2}) no son isomórficas.
\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}