\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{xcolor} 
\usepackage{wrapfig} 
\usepackage{pdfsync}
% \usepackage{floatflt}
\usepackage{paralist}
% \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}
}

\usepackage{pgf,tikz}
\usetikzlibrary{arrows}

\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 I}{Primera tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas.

\begin{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 $A(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 $A(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 $A(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 $A(G)$.
 \end{enumerate}
 \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 Muestra que hay once gráficas no isomorfas de cuatro vértices.
 \item Prueba que la suma de un conjunto de números enteros impares es par si y sólo si el número de sumandos es par.
 \item Dada $G$ una gráfica de tamaño $m$, prueba que 
\begin{displaymath}
 \sum_{v \in V(G)} d(v) = 2m
\end{displaymath}
mediante inducción sobre el tamaño de la gráfica.
 \item Si $G$ es una gráfica de orden $n$ y tamaño $m$, prueba que
  \begin{displaymath}
   m \leq \binom{n}{2}
  \end{displaymath}
  y determina cuándo se da la igualdad.
 \item Prueba que en cualquier grupo de amigos (en el que la relación de amistad sea reflexiva) siempre existen dos personas que tienen 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?
 \item Si $G$ es una gráfica bipartita con partes $X$ y $Y$ tales que $\lvert X \rvert=r$ y $\lvert Y \rvert = s$,
 \begin{enumerate}
  \item muestra que $m \leq rs$,
  \item deduce que $m \leq \frac{n^2}{4}$ y
  \item describe las gráficas bipartitas para las cuáles se la igualdad en $(b)$.
 \end{enumerate}
 \item El grado promedio de una gráfica $G$ se define como: $$d(G):=\frac{1}{n}\sum_{v\in V(G)}d(v)\text{,}$$ muestra que $\delta(G)\leq d(G) \leq \Delta(G)$.
\end{enumerate}
 

\end{document}