\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{graphicx}
\usepackage{color} 
\usepackage{wrapfig} 
\usepackage{pdfsync}
% \usepackage{floatflt}
% \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}
}

\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{Teoría de las Gráficas}{Cuarta lista de ejercicios\\22 de octubre de 2010}

\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 grádo máximo es mayor o igual a 4.
\end{enumerate}

  \item Un bosque es una gráfica acíclica. 
\begin{enumerate}
  \item Dibuja todos los bosques no isomorfos de orden 6. 
	\item Prueba que toda componente conexa de un bosque es un árbol. 
	\item Sea $B$ un bosque de orden $n$ y tamaño $m$, con $\omega$ componentes conexas. Prueba que $n=m+\omega$.
\end{enumerate}
  
  \item 
\begin{enumerate}
	\item Muestra que todo árbol de grado máximo $k$, tiene al menos $k$ vértices terminales.
	\item ¿Qué árboles tienen exactamente $k$ vértices terminales?
\end{enumerate}

  \item Sea $G$ una gráfica de orden $n$ y tamaño $m$, con la propiedad de que $n=m+1$. Prueba que $G$ no necesariamente es un árbol.
  
  \item Sea $T$ un árbol de orden $n$ tal que $d(v)\in \{1,3\}$, para todo $v\in V(T)$. Prueba que $T$ contiene $\frac{n-2}{2}$ vértices de grado $3$.
  
  \item Sea $T$ un árbol de orden $21$, con conjunto de grados $\{1,3,5,6\}$. Suponga que $T$ tiene $15$ vértices terminales y un vértice de grado $6$. ¿Cuántos vértices de grado $5$ tiene $T$?

%   \item
% \begin{enumerate}
%   \item \textit{Diga si el siguiente enunciado es verdadero o falso. En caso de ser verdadero demuéstrelo, en caso de ser falso de un contraejemplo}.\\
%    Si $(d_{1},d_{2},\dots,d_{n})$ es la sucesión de grados de un árbol, entonces $(1,d_{1}+1,d_{2},\dots,d_{n})$ es la sucesión de grados de un árbol.
%   \item Muestra que la sucesión $(d_{1},d_{2},\dots ,d_{n})$ de enteros positivos, es una sucesión de grados de un árbol si y sólo si $\sum_{i=1}^{n}{d_{i}}=2(n-1)$.
% \end{enumerate} 

  \item Encuentre todos los árboles $T$ tales que $T^{c}$ es un árbol.  
  
  \item Encuentre una fórmula para determinar el número de vértices terminales de un árbol de orden $n$, tal que los vértices que no son terminales tienen el mismo grado.
  
  \item 
\begin{enumerate}
  \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{enumerate}

\end{enumerate}

\section*{Extras}


\begin{enumerate}
\item Considera $T$ un árbol y $n_i$ el número de vértices de grado $i$ en $T$.  ¿Cuáles de las siguientes afirmaciones son verdadera?
\begin{itemize}
\item Si $T$ no es una trayectoria entonces $n_1 \geq n_2$.
\item Si $n_2=0$ entonces $T$ tiene más hojas que otros vértices.
\end{itemize}
  \item 
\begin{enumerate}
  \item Muestra que el centro de cualquier árbol es $K_{1}$ o $K_{2}$. 
  
  \item Sea $T$ un árbol y $T'$ el árbol que se obtiene de $T$ al borrar todos sus vértices terminales, muestra que $T$ y $T'$ tienen el mismo centro.
\end{enumerate}

  \item Pruebe 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.
  
  \item Pruebe que el número de vértices terminales de un árbol no trivial $T$, con $V(T)=\{v_{1},v_{2},\dots,v_{n}\}$ es: $$2+\sum_{d(v_{i})\geq 3}{(d(v_{i})-2)}$$
\end{enumerate}

\end{document}