\documentclass[letterpaper, 12pt]{article}
\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{latexsym} 
\usepackage{amssymb}  
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath} 
\usepackage{graphicx}
\usepackage{color} 
\usepackage{wrapfig} 
\usepackage{pdfsync}
\usepackage{floatflt}
\usepackage{makeidx}
\usepackage{ifpdf}
\usepackage{graphfig}
\usepackage{subfig}
\usepackage{graphicx} 
\usepackage{mathrsfs}
\usepackage{caption} 
\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\\23 de agosto de 2010}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. Se entrega por equipos de hasta dos personas.

\begin{enumerate}
	\item
\begin{enumerate}	
	\begin{sloppypar}	
	\item Dibuja la gráfica cuyo conjunto de vértices es $V(G)=\{u_{1},u_{2},u_{3},u_{4},u_{5}\}$ y conjunto de aristas $E(G)=\{u_{1}u_{2},u_{1}u_{4},u_{1}u_{5},u_{2}u_{3},u_{3}u_{5}\}$.
	\end{sloppypar}
	\begin{sloppypar}
  \item Dibuja una gráfica cuyo conjunto de vértices es $V(G)=\{u_{1},u_{2},u_{3},u_{4},u_{5}\}$ y cuyo conjunto de aristas $E(G)$ es tal que $\left|E(G)\right|$ es lo más grande posible. Determina el conjunto $E$.
	\end{sloppypar}
	\item Si una gráfica es de orden $3$, ¿cuáles son los posibles tamaños de $G$?
	\item Cuál es el tamaño máximo posible de una gráfica cuyo orden es $n$, donde $n$ es un entero positivo?
\end{enumerate}
	\item ¿Existe una gráfica $G$ de orden $5$ o más que cumpla que cada vértice de $G$ incide al menos una arista, pero no sucede que cualesquiera dos aristas son adyacentes? (Justifica su respuesta.)
	\item Da un ejemplo de una gráfica $G$ de tamaño positivo con la propiedad de que cualquier vértice incide en cualquier arista.
	\item Da un ejemplo de una gráfica que cumpla las siguientes propiedades:
\begin{enumerate}
	\item todo vértice es adyacente a dos vértices; y
	\item toda arista es adyacente a dos aristas.
\end{enumerate}
\item
\begin{enumerate}
 \item Considera 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)$.
 \end{enumerate}
 \item Muestre que para cualquier gráfica $G$, $m\leq \left(\begin{aligned} &n\\ &2 \end{aligned}\right)$.
 \item Etiquete las siguientes gráficas y describa el conjunto de vértices y el conjunto de aristas para cada una. Encuentre su matriz de adyacencia y su matriz de incidencia:
 \begin{figure}[ht]
\centering
\subfloat[$G_{1}$]{
  \label{fig:c9:a}
  \includegraphics[totalheight=3cm]{c9}}
\hspace{0.2\linewidth}
\subfloat[$G_{2}$]{
  \label{fig:k6:b}
  \includegraphics[totalheight=3cm]{k6}}  
\hspace{0.2\linewidth}
\subfloat[$G_{3}$]{
  \label{fig:k17:c}
  \includegraphics[totalheight=3cm]{k17}}
\hspace{0.2\linewidth}
\subfloat[$G_{4}$]{
  \label{fig:petersen:d}
  \includegraphics[totalheight=3cm]{petersen}}
\hspace{0.2\linewidth}
\subfloat[$G_{5}$]{
  \label{fig:t5:e}
  \includegraphics[totalheight=3cm]{t5}}
\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}
 
\end{enumerate}
 

\end{document}