\documentclass[letterpaper, 12pt]{article}
  \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.

\begin{enumerate}
	\item Prueba con la matriz de incidencia que la suma de los grados de los vértices de una gráfica es igual a dos veces el número de aristas.
	\item Prueba que todo paseo cerrado posee un ciclo.
	\item Prueba que la unión de paseos distintos con los mismos extremos posee un ciclo.
	\item Dibuja todas las gráficas conexas no isomorfas con cinco vértices. Da algunos ejemplos de gráficas no conexas con seis vértices.
	\item Considera una gráfica bipartita $G$ con bipartición $V_1$, $V_2$. Si $x$ y $y$ son vértices de $G$ prueba que:
	\begin{enumerate}
		\item Si $x$, $y \in V_i$, para $i\in\{1$, $2\}$, entonces toda trayectoria entre $x$ y $y$ es de longitud par.
		\item Si $x \in V_i$ y $y \in V_j$, para $i$, $j \in \{1$, $2\}$ e $i \neq j$, entonces toda trayectoria entre $x$ y $y$ es de longitud impar.
	\end{enumerate}
	\item Prueba que $G$ es conexa si y sólo si posee un camino \emph{cerrado} que pasa por todos los vértices de $G$.
	\item Prueba que $G$ es conexa si y sólo si posee un camino \emph{abierto} que pasa por todos los vértices de $G$.
	\item Muestra que no existe una gráfica con siete 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 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 Muestra que el complemento de una gráfica bipartita no necesariamente es bipartita.
\end{enumerate}
 


\section*{Extras}
\begin{enumerate}[A.]

 \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}

\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 dos gráficas, con seis vértices, tal que todos sus vértices tengan grado dos pero que no sean isomorfas entre sí.

 \item Muestra que si $G$ es autocomplementaria entonces su orden es múltiplo de cuatro o múltiplo de cuatro más uno.
\end{enumerate}

\end{document}
