\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{graphics}
\usepackage{color}
\usepackage[all]{xy}
\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}{Segunda tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. La tarea es individual, \textbf{no se aceptarán tareas que no cumplan este requisito}. Resuelve al menos \textbf{catorce} problemas.
\paragraph{ }
Recuerden que las definiciones son las importantes. Para probar algo no siempre es bueno sobreargumentar (ni tampoco quedar falto de argumentos). Los mejores argumentos suelen ser los simples.

\begin{enumerate}
\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 el número de aristas.

\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 el número de aristas.

\item Muestra que:
\begin{displaymath}
 \delta(G) \leq d(v) \leq \Delta(G)
\end{displaymath}
para cualquier vértice $v$\footnote{Sí, ya sé. Algunos ejercicios pueden parecer algo simples u obvios, pero como les dije, esta materia es para que aprendan a escribir, aunque sea obvio. Pero recuerden, pueden substituir cualquier problema con alguno de los extras n\_n}.

 \item El número
\begin{displaymath}
d(G):=\frac{1}{\lvert V(G)\rvert}\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 Dibuja las once gráficas no isomorfas 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 $uv \in A(\overline{G})$ si y sólo $uv \notin A(G)$ (siempre que $u \neq v$).
\end{compactitem}
\begin{compactenum}
\item Muestra que $\overline{G}$ es también una gráfica.
\item Si $G$ y $H$ son isomorfas ¿entonces $\overline{G}$ y $\overline{H}$ son isomorfas?
\item Si $H$ es subgráfica de $G$ ¿entonces $\overline{H}$ es subgráfica de $\overline{G}$?
\end{compactenum}

\item Una gráfica es \emph{autocomplementaria} si $G\cong \overline{G}$.  Dibuja \textbf{todas} las gráficas autocomplementarias de orden menor o igual que cinco.
 
 \item Muestra dos gráficas, con seis vértices, tal que todos sus vértices tengan grado dos pero que no sean isomorfas entre sí.

 \item ¿Las siguientes tres gráficas son o no isomorfas? Argumenta porqué no o prueba porqué sí.

\definecolor{qqqqff}{rgb}{0.49,0.49,1}
\definecolor{qqqqff}{rgb}{0,0,1}
\begin{figure}[!h]
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.75cm,y=0.75cm]
% \clip(-1.32,-4.04) rectangle (18.18,6.3);
\draw (0.48,2.52)-- (2.44,4.18);
\draw (2.44,4.18)-- (4.52,2.5);
\draw (4.52,2.5)-- (3.76,0);
\draw (3.76,0)-- (1.36,0);
\draw (1.36,0)-- (0.48,2.52);
\draw (1.64,2.1)-- (3.22,2.1);
\draw (3.22,2.1)-- (2,1);
\draw (2.44,2.88)-- (2,1);
\draw (2.44,2.88)-- (3,1);
\draw (3,1)-- (1.64,2.1);
\draw (2.44,4.18)-- (2.44,2.88);
\draw (1.64,2.1)-- (0.48,2.52);
\draw (2,1)-- (1.36,0);
\draw (3,1)-- (3.76,0);
\draw (3.22,2.1)-- (4.52,2.5);
\draw(8.5,1.66) circle (1.6cm);
\draw (8.5,3.79)-- (8.5,1.66);
\draw (8.5,1.66)-- (6.66,0.59);
\draw (10.09,3.08)-- (7.62,-0.28);
\draw (8.5,1.66)-- (10.34,0.59);
\draw (6.91,3.08)-- (9.48,-0.23);
\draw (6.4,2)-- (10.6,2.02);
\draw (14.42,2.6)-- (14.48,1.66);
\draw (14.48,1.66)-- (13.84,1.22);
\draw (14.48,1.66)-- (15.2,1.26);
\draw (12.38,1.48)-- (14.42,2.6);
\draw (14.42,2.6)-- (16.56,1.5);
\draw (13.44,3.76)-- (15.7,3.74);
\draw (15.7,3.74)-- (16.56,1.5);
\draw (16.56,1.5)-- (15.62,-0.14);
\draw (15.62,-0.14)-- (13.54,-0.14);
\draw (13.54,-0.14)-- (12.38,1.48);
\draw (13.44,3.76)-- (12.38,1.48);
\draw (13.44,3.76)-- (13.84,1.22);
\draw (15.2,1.26)-- (15.7,3.74);
\draw (13.84,1.22)-- (15.62,-0.14);
\draw (15.2,1.26)-- (13.54,-0.14);
\fill [color=qqqqff] (2,1) circle (1.5pt);
\fill [color=qqqqff] (1.64,2.1) circle (1.5pt);
\fill [color=qqqqff] (2.44,2.88) circle (1.5pt);
\fill [color=qqqqff] (3,1) circle (1.5pt);
\fill [color=qqqqff] (3.22,2.1) circle (1.5pt);
\fill [color=qqqqff] (1.36,0) circle (1.5pt);
\fill [color=qqqqff] (3.76,0) circle (1.5pt);
\fill [color=qqqqff] (4.52,2.5) circle (1.5pt);
\fill [color=qqqqff] (0.48,2.52) circle (1.5pt);
\fill [color=qqqqff] (2.44,4.18) circle (1.5pt);
\fill [color=qqqqff] (8.5,1.66) circle (1.5pt);
\fill [color=qqqqff] (7.62,-0.28) circle (1.5pt);
\fill [color=qqqqff] (9.48,-0.23) circle (1.5pt);
\fill [color=qqqqff] (6.66,0.59) circle (1.5pt);
\fill [color=qqqqff] (10.34,0.59) circle (1.5pt);
\fill [color=qqqqff] (6.4,2) circle (1.5pt);
\fill [color=qqqqff] (10.6,2.02) circle (1.5pt);
\fill [color=qqqqff] (6.91,3.08) circle (1.5pt);
\fill [color=qqqqff] (10.09,3.08) circle (1.5pt);
\fill [color=qqqqff] (8.5,3.79) circle (1.5pt);
\fill [color=qqqqff] (14.48,1.66) circle (1.5pt);
\fill [color=qqqqff] (14.42,2.6) circle (1.5pt);
\fill [color=qqqqff] (13.84,1.22) circle (1.5pt);
\fill [color=qqqqff] (15.2,1.26) circle (1.5pt);
\fill [color=qqqqff] (12.38,1.48) circle (1.5pt);
\fill [color=qqqqff] (16.56,1.5) circle (1.5pt);
\fill [color=qqqqff] (13.54,-0.14) circle (1.5pt);
\fill [color=qqqqff] (15.62,-0.14) circle (1.5pt);
\fill [color=qqqqff] (13.44,3.76) circle (1.5pt);
\fill [color=qqqqff] (15.7,3.74) circle (1.5pt);
\end{tikzpicture}
\end{figure}

 Una gráfica $G$ se dice \emph{bipartita} si existe una partición $\{X$, $Y\}$ del conjunto de sus vértices (\textit{i.e.}, $X$, $Y\subseteq V(G)$, $X \cap Y = \emptyset$ y $X \cup Y = V(G)$, a tales conjuntos se les llama las \emph{partes} de la bipartición) que satisfaga que toda arista de $G$ tiene extremos en partes \textbf{distintas}. Es decir, ninguna arista tiene ambos extremos en la misma parte.

 \item Muestra que el complemento de una gráfica bipartita no necesariamente es bipartita.
 \item Muestra que toda trayectoria (es decir, las gráficas formadas por exclusivamente una trayectoria) es bipartita.
 \item Prueba que si $G$ es bipartita y $H$ es una gráfica isomorfa a $G$ entonces $H$ es bipartita.
 \item Muestra\footnote{Si ya hiciste este problema como extra en la tarea pasada, no es necesario que lo repitas, nomás recuérdanoslo.} 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 Considera $G$ una gráfica, ¿cómo se relacionan, en términos de cardinalidades, $V(G)$ y $V(\overline{H})$? ¿$A(G)$ y $A(\overline{G})$? ¿Y si además suponemos que $G$ es autocomplementaria?
 \item Caracteriza (es decir, describe \emph{cómo} son) todas las gráficas:
\begin{enumerate}
 \item $0$-regulares,
 \item $1$-regulares y
 \item $2$-regulares.
\end{enumerate}

 \item Etiqueta las siguientes gráficas y describe el conjunto de vértices y el conjunto de aristas para cada una. Encuentra su matriz de adyacencia y su matriz de incidencia:

\begin{figure}[!h]
	\begin{minipage}[b]{0.5\linewidth}
	\centering
\definecolor{qqqqff}{rgb}{0.49,0.49,1}
\definecolor{qqqqff}{rgb}{0,0,1}
\definecolor{ffffff}{rgb}{1,1,1}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.75cm,y=0.75cm]
% \clip(-4.3,-4.04) rectangle (8.42,6.3);
\draw [color=ffffff] (4,3) circle (1.58cm);
\draw (1.95,3.52)-- (2.05,2.19);
\draw (2.05,2.19)-- (3.32,1);
\draw (3.32,1)-- (4.67,1);
\draw (4.67,1)-- (5.96,2.2);
\draw (6.04,3.54)-- (5.96,2.2);
\draw (5.39,4.59)-- (6.04,3.54);
\draw (4,5.11)-- (5.39,4.59);
\draw (2.65,4.62)-- (4,5.11);
\draw (2.65,4.62)-- (1.95,3.52);
\draw [color=ffffff] (4,3) circle (0.5pt);
\fill [color=qqqqff] (3.32,1) circle (1.5pt);
\fill [color=qqqqff] (4.67,1) circle (1.5pt);
\fill [color=qqqqff] (2.05,2.19) circle (1.5pt);
\fill [color=qqqqff] (5.96,2.2) circle (1.5pt);
\fill [color=qqqqff] (1.95,3.52) circle (1.5pt);
\fill [color=qqqqff] (6.04,3.54) circle (1.5pt);
\fill [color=qqqqff] (2.65,4.62) circle (1.5pt);
\fill [color=qqqqff] (5.39,4.59) circle (1.5pt);
\fill [color=qqqqff] (4,5.11) circle (1.5pt);
\end{tikzpicture}
	\end{minipage}
	\hspace{0.25cm}
	\begin{minipage}[b]{0.5\linewidth}
	\centering
\definecolor{qqqqff}{rgb}{0,0,1}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.5cm,y=1.5cm]
% \clip(-4.3,-6.56) rectangle (16.16,6.3);
\draw (3,3)-- (4.02,3.52);
\draw (5,3)-- (3,2);
\draw (3,3)-- (3,2);
\draw (3,2)-- (4,1.5);
\draw (4,1.5)-- (5,2);
\draw (5,2)-- (5,3);
\draw (5,3)-- (4.02,3.52);
\draw (4.02,3.52)-- (4,1.5);
\draw (3,2)-- (5,2);
\draw (5,2)-- (3,3);
\draw (3,3)-- (5,3);
\fill [color=qqqqff] (3,2) circle (1.5pt);
\fill [color=qqqqff] (3,3) circle (1.5pt);
\fill [color=qqqqff] (4,1.5) circle (1.5pt);
\fill [color=qqqqff] (5,2) circle (1.5pt);
\fill [color=qqqqff] (5,3) circle (1.5pt);
\fill [color=qqqqff] (4.02,3.52) circle (1.5pt);
\end{tikzpicture}
	\end{minipage}
	\end{figure}

\begin{figure}[!h]
	\begin{minipage}[b]{0.5\linewidth}
	\centering
\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,-6.56) rectangle (16.16,6.3);
\draw (4,4.42)-- (4,3);
\draw (4,3)-- (2.8,2.52);
\draw (2.92,3.78)-- (4,3);
\draw (4,3)-- (3.48,1.6);
\draw (4,3)-- (4.6,1.6);
\draw (4,3)-- (5.34,2.4);
\draw (4,3)-- (5.12,3.78);
\fill [color=qqqqff] (4,3) circle (1.5pt);
\fill [color=qqqqff] (4,4.42) circle (1.5pt);
\fill [color=qqqqff] (2.92,3.78) circle (1.5pt);
\fill [color=qqqqff] (5.12,3.78) circle (1.5pt);
\fill [color=qqqqff] (2.8,2.52) circle (1.5pt);
\fill [color=qqqqff] (5.34,2.4) circle (1.5pt);
\fill [color=qqqqff] (3.48,1.6) circle (1.5pt);
\fill [color=qqqqff] (4.6,1.6) circle (1.5pt);
\end{tikzpicture}

	\end{minipage}
	\hspace{0.25cm}
	\begin{minipage}[b]{0.5\linewidth}
	\centering

\definecolor{qqqqff}{rgb}{0,0,1}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
% \clip(-1.32,-4.04) rectangle (18.18,6.3);
\draw (0.48,2.52)-- (2.44,4.18);
\draw (2.44,4.18)-- (4.52,2.5);
\draw (4.52,2.5)-- (3.76,0);
\draw (3.76,0)-- (1.36,0);
\draw (1.36,0)-- (0.48,2.52);
\draw (1.64,2.1)-- (3.22,2.1);
\draw (3.22,2.1)-- (2,1);
\draw (2.44,2.88)-- (2,1);
\draw (2.44,2.88)-- (3,1);
\draw (3,1)-- (1.64,2.1);
\draw (2.44,4.18)-- (2.44,2.88);
\draw (1.64,2.1)-- (0.48,2.52);
\draw (2,1)-- (1.36,0);
\draw (3,1)-- (3.76,0);
\draw (3.22,2.1)-- (4.52,2.5);
\fill [color=qqqqff] (2,1) circle (1.5pt);
\fill [color=qqqqff] (1.64,2.1) circle (1.5pt);
\fill [color=qqqqff] (2.44,2.88) circle (1.5pt);
\fill [color=qqqqff] (3,1) circle (1.5pt);
\fill [color=qqqqff] (3.22,2.1) circle (1.5pt);
\fill [color=qqqqff] (1.36,0) circle (1.5pt);
\fill [color=qqqqff] (3.76,0) circle (1.5pt);
\fill [color=qqqqff] (4.52,2.5) circle (1.5pt);
\fill [color=qqqqff] (0.48,2.52) circle (1.5pt);
\fill [color=qqqqff] (2.44,4.18) circle (1.5pt);
\end{tikzpicture}
	\end{minipage}
	\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 Muestra que la siguiente gráfica es autocomplementaria:
\begin{figure}[!h]
\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 (15.2,6.3);
\draw (4,4)-- (5,4);
\draw (5,4)-- (6,3);
\draw (6,3)-- (6,2);
\draw (6,2)-- (5,1);
\draw (5,1)-- (4,1);
\draw (4,1)-- (3,2);
\draw (3,2)-- (3,3);
\draw (3,3)-- (4,4);
\draw (3,3)-- (4,1);
\draw (4,1)-- (6,2);
\draw (6,2)-- (5,4);
\draw (5,4)-- (3,3);
\draw (4,4)-- (5,1);
\draw (3,2)-- (6,3);
\fill [color=qqqqff] (3,3) circle (1.5pt);
\fill [color=qqqqff] (3,2) circle (1.5pt);
\fill [color=qqqqff] (4,1) circle (1.5pt);
\fill [color=qqqqff] (5,1) circle (1.5pt);
\fill [color=qqqqff] (6,2) circle (1.5pt);
\fill [color=qqqqff] (6,3) circle (1.5pt);
\fill [color=qqqqff] (4,4) circle (1.5pt);
\fill [color=qqqqff] (5,4) circle (1.5pt);
\end{tikzpicture}
\end{figure}
 \item Muestra que toda gráfica bipartita completa $K_{p,q}$, con $p=\lvert X\rvert$ y $q=\lvert Y\rvert$, donde $X$ e $Y$ son los elementos de la bipartición, se puede obtener usando la suma de gráficas. Determina qué gráficas deben sumarse para construir a $K_{p,q}$.


\end{enumerate}

\section*{Extras}
\begin{enumerate}[A.]
 \item Prueba que $G_1$ y $G_2$ (Figuras~\ref{fig:g1} y \ref{fig:g2}) \emph{no} son isomorfas.

\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.6,1) }*{\bullet}="1"
	!{(0.3,-0.1) }*{\bullet}="3"
	!{(0.9,-0.1) }*{\bullet}="4"
	!{(0.9,0.8) }*{\bullet}="6"
	!{(1.1,1) }*{\bullet}="6b"
	!{(1.3,1.2) }*{\bullet}="7"
	!{(1.2,0.55) }*{\bullet}="5"
	!{(1.3,-0.5) }*{\bullet}="8"
	"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"
	!{(1.2,0.55) }*{\bullet}="5"
	!{(1.3,-0.5) }*{\bullet}="8"
	"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}

 \item Demuestra que las siguientes gráficas \emph{no} son isomorfas:
\begin{figure}[!h]
\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,-6.56) rectangle (15.88,6.3);
\draw (1,4)-- (1,1);
\draw (1,1)-- (4,1);
\draw (4,1)-- (3,2);
\draw (3,2)-- (2,2);
\draw (2,2)-- (1,1);
\draw (2,3)-- (2,2);
\draw (2,3)-- (3,3);
\draw (3,3)-- (3,2);
\draw (3,3)-- (4,4);
\draw (4,4)-- (4,1);
\draw (1,4)-- (2,3);
\draw (1,4)-- (4,4);
\draw (6,3)-- (6,2);
\draw (6,2)-- (7,1);
\draw (7,1)-- (8,1);
\draw (8,1)-- (9,2);
\draw (9,2)-- (9,3);
\draw (9,3)-- (8,4);
\draw (8,4)-- (7,4);
\draw (7,4)-- (6,3);
\draw (7,4)-- (8,1);
\draw (8,4)-- (7,1);
\draw (6,3)-- (9,2);
\draw (9,3)-- (6,2);
\fill [color=qqqqff] (1,1) circle (1.5pt);
\fill [color=qqqqff] (2,2) circle (1.5pt);
\fill [color=qqqqff] (2,3) circle (1.5pt);
\fill [color=qqqqff] (3,3) circle (1.5pt);
\fill [color=qqqqff] (3,2) circle (1.5pt);
\fill [color=qqqqff] (4,4) circle (1.5pt);
\fill [color=qqqqff] (4,1) circle (1.5pt);
\fill [color=qqqqff] (1,4) circle (1.5pt);
\fill [color=qqqqff] (6,3) circle (1.5pt);
\fill [color=qqqqff] (6,2) circle (1.5pt);
\fill [color=qqqqff] (7,1) circle (1.5pt);
\fill [color=qqqqff] (8,1) circle (1.5pt);
\fill [color=qqqqff] (9,2) circle (1.5pt);
\fill [color=qqqqff] (9,3) circle (1.5pt);
\fill [color=qqqqff] (8,4) circle (1.5pt);
\fill [color=qqqqff] (7,4) circle (1.5pt);
\end{tikzpicture}
\end{figure}

 \item Calcula el orden y el tamaño del $k$-cubo.

 \item Prueba que el $k$-cubo es bipartito.

 \item Muestra que si $G$ es autocomplementaria entonces su orden es múltiplo de cuatro o múltiplo de cuatro más uno (\emph{Sugerencia}. Revisa el problema cuarto).

 \item Si $G$ es una gráfica bipartita con bipartición $X$, $Y$ con $\lvert X \rvert = p$ y $\lvert Y \rvert = q$. Prueba que el tamaño de $G$ es menor o igual que $pq$.

 \item Prueba, mediante el uso de gráficas, que:
\begin{displaymath}
 1+2+\ldots+n=\frac{n(n+1)}{2}\text{.}
\end{displaymath}


\end{enumerate}

\end{document}