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

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

\begin{enumerate}
 \item Prueba que toda gráfica conexa posee un subárbol generador. No olvides decir explícitamente qué entendemos por \emph{subárbol generador}.
 \item Prueba que si $G$ es un árbol con al menos dos vértices entonces tiene al menos dos hojas.
 \item Prueba que si $G$ es un árbol con al menos tres vértices y $T_0$ es el conjunto de todos los vértices de grado uno de $T$ (es decir, es el conjunto de todas sus hojas) entonces $G-T_0$ es un árbol. No olvides decir explícitamente qué se entiende por $G-T_0$ y no olvides la definición de árbol.
 \item Sean $u$ y $v$ vértices de una gráfica conexa $G$. Se define la distancia $d(u$, $v)$ entre $u$ y $v$ como la mínima de entre las longitudes de todas las posibles $uv$-trayectorias en $G$. Prueba que $d$ es una métrica para $V(G)$, es decir,
\begin{compactenum}
 \item $d(u$, $v) \geq 0$ para cualesquiera $u$ y $v$ en $V(G)$ y $d(u$, $v) = 0$ si y sólo
si $u = v$,
 \item $d(u$, $v) = d(v$, $u)$ para cualesquiera $u$ y $v$ en $V(G)$ y
 \item $d(u$, $w) \leq d(u$, $v) + d(v$, $w)$ para cualesquiera $u$ y $v$ en $V(G)$.
\end{compactenum}
 \item Prueba que si $T$ es un árbol entonces el centro de $T$ es el mismo que el centro de $T-T_0$ (donde $T_0$ es el conjunto de todas las hojas de $T$).
 \item Considera $T$ un árbol y $u$ un vértice de $T$. Muestra que existe una trayectoria $P=(u=x_0$, $x_1$, \ldots, $x_n)$ de longitud $e_T(u)$ en $T$ y que $x_n$ en dicha trayectoria es una hoja de $T$.
 \item Prueba que el centro de un árbol es $K_1$ o $K_2$.
 \item Un \emph{bosque} es una gráfica acíclica. Prueba que toda componente de un bosque es un árbol y que si $\omega$ denota el número de componentes conexas de una gráfica entonces en un bosque se tiene que:
\begin{displaymath}
 q = p - \omega\text{.}
\end{displaymath}
 \item Prueba que todo árbol con al menos dos vértices es bipartito al dar \textbf{explícitamente} una bipartición de sus vértices y al mostrar que efectivamente es una bipartición.
 \item Considera una gráfica $G$ con $p$ vértices y $q$ aristas tales que $q \geq p \geq 3$. Muestra que $G$ posee al menos un ciclo.

\end{enumerate}

\section*{Extras}

\begin{enumerate}[A.]
 \item Considera una gráfica conexa $G$ y $a$ una arista acíclica de $G$. Prueba que $a$ está en todo subárbol generador de $G$.
 \item Muestra que el centro de un árbol es $K_1$ si la trayectoria de longitud máxima es de longitud par y que el centro es $K_2$ si la longitud de la trayectoria de longitud máxima es impar.
 \item
 \begin{compactenum}
 \item Pruebe que un árbol tiene exactamente dos hojas si y sólo si es una trayectoria.
 \item Pruebe que un árbol tiene diámetro 2 si y sólo si es una estrella.
 \end{compactenum}
 \item Muestra que todo árbol tiene al menos $\Delta$ hojas.
 \item Prueba que una gráfica $G$ es un bosque si y sólo si toda subgráfica inducida de $G$ tiene un vértice de grado a lo más uno.
 \item Considera un árbol $T$ con $k+1$ vértices. Prueba que si $G$ es una gráfica con grado mínimo al menos $k$ entonces $G$ posee una subgráfica isomorfa a $T$.
\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}
