\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 se entrega individualmente.
\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 más simples.

\begin{enumerate}

\item 
\begin{enumerate}
\item Muestra que existe una gráfica simple con siete vértices y doce aristas tal que el grado de cada vértice es dos, tres o cuatro.
\item Muestra que no existe una gráfica simple de orden doce y tamaño veintiocho en la que el grado de cada vértice sea tres o cuatro.
\end{enumerate}

\item Considera una colección $z_1$, $z_2$, \ldots, $z_k$ de números enteros impares. Prueba que $\sum_{i=1}^k z_i$ es par si y sólo si $k$ es par.

\item
\begin{enumerate}
\item Encuentra la matriz de adyacencia y la matriz de incidencia de la siguiente gráfica:

\definecolor{qqqqff}{rgb}{0,0,1}
\begin{tikzpicture}[>=triangle 45,x=0.66cm,y=0.66cm]
% \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.66cm,y=0.66cm]
% \clip(-4.3,-3.94) rectangle (8.42,6.3);
\draw (1,1)-- (1.64,3.18);
\draw (1.64,3.18)-- (4,4);
\draw (4,4)-- (6.96,3.5);
\draw (4,4)-- (4,-1);
\draw (4,4)-- (5.98,-0.22);
\draw (5.98,-0.22)-- (4,-1);
\draw (4,-1)-- (1,1);
\draw (1,1)-- (5.98,-0.22);
\draw (5.98,-0.22)-- (6.96,3.5);
\fill [color=qqqqff] (1,1) circle (1.5pt);
\draw[color=qqqqff] (0.68,1.22) node {$v_6$};
\fill [color=qqqqff] (1.64,3.18) circle (1.5pt);
\draw[color=qqqqff] (1.36,3.58) node {$v_1$};
\fill [color=qqqqff] (4,4) circle (1.5pt);
\draw[color=qqqqff] (4.18,4.52) node {$v_2$};
\fill [color=qqqqff] (6.96,3.5) circle (1.5pt);
\draw[color=qqqqff] (7.4,3.84) node {$v_3$};
\fill [color=qqqqff] (4,-1) circle (1.5pt);
\draw[color=qqqqff] (3.94,-1.16) node {$v_5$};
\fill [color=qqqqff] (5.98,-0.22) circle (1.5pt);
\draw[color=qqqqff] (6.42,-0.3) node {$v_4$};
\end{tikzpicture}
% \begin{figure}[h]
% 	\centering
% 		\includegraphics[totalheight=3cm]{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}
\end{enumerate}

\item Caracteriza todas las gráficas $k$-regulares para $k=0,1,2$.

\item Prueba que si todo vértice en un gráfica $G$ tiene al menos grado uno (es decir, $\delta(G) \geq 1$) entonces $G$ tiene al menos $\lceil n/2 \rceil$ aristas (es decir, $m \geq \lceil n/2 \rceil$,donde $\lceil x \rceil$ es el \emph{menor entero mayor o igual que $x$}. \emph{Sugerencia.} Pruébalo primero para gráfica de orden par, para esto usa la suma de los grados de los vértices, luego ajusta la prueba para gráficas de orden impar).

\end{enumerate}

\textsc{Extras:}

\begin{enumerate}

\item Muestra que toda gráfica simple de orden $n$ es isomorfa a una subgráfica de $K_{n}$.
\item El $n$-cubo $Q_{n}$ ($n\geq 1$) es la gráfica definida de manera recursiva como:
$Q_{1}=K_{2}$ y $Q_{n}=K_{2}\times Q_{n-1}$. Prueba que
\begin{enumerate}
\item Determina el número de vértices y el número de aristas del $n$-cubo.
\item Prueba que el $n$-cubo es bipartita.
\end{enumerate}

\end{enumerate}


\end{document}