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

\usepackage{pgf,tikz}
\usetikzlibrary{arrows}

\theoremstyle{definition}
\newtheorem{definicion}[proposicion]{Definición}

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\mcd}{mcd}

\begin{document}
\header{Gráficas y juegos}{Cuarta 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 simples.

\begin{enumerate}

\item
\begin{enumerate}
\item Dibuja todos los árboles no isomorfos de orden 6.
\item Dibuja todos los árboles no isomorfos de orden 7 tales que su grado máximo sea menor o igual a 4.
\end{enumerate}

\item Determina todos los diferentes árboles generadores no isomorfos de la siguiente gráfica:
\begin{figure}[h]
	\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,-4.04) rectangle (8.42,6.3);
\draw (1.48,2.98)-- (2,1);
\draw (2,1)-- (4,1);
\draw (3,4.32)-- (4.52,3);
\draw (4.52,3)-- (4,1);
\draw (1.48,2.98)-- (3,4.32);
\draw (1.48,2.98)-- (4,1);
\draw (2,1)-- (4.52,3);
% \draw (0.9,3.7) node[anchor=north west] {$v_1$};
% \draw (1.35,1.15) node[anchor=north west] {$v_2$};
% \draw (4,1) node[anchor=north west] {$v_3$};
% \draw (4.48,3.6) node[anchor=north west] {$v_4$};
% \draw (2.4,5) node[anchor=north west] {$v_5$};
\fill [color=qqqqff] (2,1) circle (1.5pt);
\fill [color=qqqqff] (4,1) circle (1.5pt);
\fill [color=qqqqff] (1.48,2.98) circle (1.5pt);
\fill [color=qqqqff] (3,4.32) circle (1.5pt);
\fill [color=qqqqff] (4.52,3) circle (1.5pt);
\end{tikzpicture}
\end{figure}


\item ¿Es posible que un árbol sea una gráfica $r$-regular? (Justifica tu respuesta.)

\item Sea $G$ una gráfica con la propiedad de que para cualesquiera dos vértices distintos $u$ y $v$ de $G$, existe exactamente una $(u$, $v)$-trayectoria. Pruebe que $G$ es un árbol.

\item Encuentre una gráfica con la siguiente propiedad: para cualesquiera dos vértices $u$ y $v$, existen exactamente dos $(u$, $v)$-trayectorias.

\item Sea $G$ una gráfica de orden $p$ y tamaño $q$ tal que $q\geq p\geq 3$. Muestra que $G$ debe contener al menos un ciclo.

\item Considera $K_{4}$ con conjunto de vértices $V(K_{4})=\{v_{1},v_{2},v_{3},v_{4}\}$. Dibuja todos los árboles generadores de $K_{4}$ que tienen a $v_{4}$ como vértice terminal.

\item Prueba que todo árbol es bipartito al dar \textbf{explícitamente} una bipartición de sus vértices y al mostrar que efectivamente es una bipartición.

\item Prueba que toda componente conexa de un bosque es un árbol.

\item Prueba que si $F$ es un bosque de orden $n$ con $\omega$ componentes conexas, entonces el tamaño de $F$ es $n-\omega$.

\end{enumerate}

\section*{Extras}
 \begin{enumerate}[A.]
\item De un ejemplo de un árbol $T$, de orden mayor o igual a 2, con la propiedad de que su complemento también es un árbol. 

\item Prueba que el centro de un árbol es $K_{1}$ o $K_{2}$.

\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 Prueba que cualquier gráfica $G$ es el centro de una gráfica conexa. (Es decir, dada una gráfica $G$, prueba que es posible encontrar una gráfica $H$ tal que el centro de $H$ sea $G$.) Sugerencia: Dada $G$, construye una gráfica $H$ tal que $V(H)=V(G)\cup \{u{1},u_{2},v_{1},v_{2}\}$ y $E(H)=E(G)\cup \{u_{1}v_{1},u_{2}v_{2}\}\cup \{u_{1}x:x\in V(G)\}\cup \{u_{2}x:x\in V(G)\}$ y prueba que cualquier vértice de $G$ tiene excentricidad mínima.

\item Prueba que una gráfica $G$ es un bosque si y sólo si toda subgráfica inducida de $G$ contiene un vértice de grado a lo más 1.
\end{enumerate}


\end{document}