\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{Gráficas y juegos}{Primera tarea}

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 $A(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 $A(G)$ sea lo más grande posible. Determina el conjunto $A(G)$.
	\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{sloppypar}
\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 tu 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 $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 El Consejo Estudiantil de cierta escuela consta de 15 miembros. Diez diferentes comités en dicha escuela están compuestos por miembros del Consejo Estudiantil. Algunos comités tienen pocos miembros, mientras que otros tienen más. Algunos Consejeros Estudiantiles no pertenecen a ningún comité y otros pertenecen a varios. Muestra dos gráficas que ejemplifiquen esta situación, para cada una describe el conjunto de vértices y la relación entre ellos.
 \item Da un ejemplo de una situación de la vida real que pueda ser representada por una gráfica. Dibuja la gráfica que describe dicha situación.
\item Ponle nombre a los vértices de la gráfica $G$ en la figura~\ref{ejercicio}, determina $d_{G}(v)$ para todo $v\in V(G)$, así como el orden $n$ y el tamaño $m$ de $G$ y verifica que $\sum_{v\in V(G)} {d_{G}(v)}=2m$.
\begin{figure}[!h]
\center
\definecolor{qqqqff}{rgb}{0,0,1}
\begin{tikzpicture}
%[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
% \clip(-4.3,-4.04) rectangle (8.42,6.3);
\draw (2,2)-- (3,3);
\draw (2,2)-- (3,1);
\draw (3,1)-- (4,2);
\draw (4,2)-- (6,2);
\draw (4,2)-- (3,3);
\draw (3,3)-- (3,1);
\draw (7,3)-- (6,2);
\draw (6,2)-- (7,1);
\draw (7,1)-- (8,2);
\draw (6,2)-- (8,2);
\fill [color=qqqqff] (2,2) circle (1.5pt);
\fill [color=qqqqff] (3,1) circle (1.5pt);
\fill [color=qqqqff] (3,3) circle (1.5pt);
\fill [color=qqqqff] (4,2) circle (1.5pt);
\fill [color=qqqqff] (6,2) circle (1.5pt);
\fill [color=qqqqff] (7,3) circle (1.5pt);
\fill [color=qqqqff] (7,1) circle (1.5pt);
\fill [color=qqqqff] (8,2) circle (1.5pt);
\end{tikzpicture}
\caption{$G$}
\label{ejercicio}
\end{figure}

 \item Muestra que no exista una gráfica con vértices de grado:
 \begin{enumerate}
  \item $3$, $3$, $4$, $4$, $5$, $5$, $5$.
  \item $1$, $2$, $3$, $4$, $5$, $6$, $7$.
  \item $0$, $2$, $2$, $3$, $4$, $5$, $6$.
 \end{enumerate}

 \item \begin{enumerate}
  \item Encuentra una gráfica $3$-regular con diez vértices.
  \item Explica porque no puede existir una gráfica $3$-regular con once vértices.
       \end{enumerate}
 \item ¿Es posible determinar el orden y el tamaño de una gráfica si se conocen los grados de todos sus vértices? Justifica su respuesta.

 \item ¿Es posible determinar los grados de los vértices de una gráfica si se conocen el orden y el tamaño de la misma? Justifique su respuesta.
\end{enumerate}

\section*{Extras}
\begin{enumerate}[A.]
 \item Muestra que $m \leq \frac{n(n-1)}{2}$. (\emph{Sugerencia.} Considera cómo es el grado máximo en una gráfica, el grado de todo vértice de la gráfica en cuestión y el teorema de la suma de los grados).
 \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 (no se vale usar ningún teorema directamente).
 \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{document}