\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{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{Teoría de Gráficas}{Tercera tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas\hyphenation{res-pues-tas}. Se entrega en equipos de exactamente dos personas.

\begin{enumerate}
	\item Demuestra que si $v$ es un vértice de corte en una gráfica conexa $G$ entonces $v$ no es de corte en $G^{c}$
	
	\item Un \textit{elemento} de una gráfica $G$ es un vértice o una arista. Prueba que una gráfica $G$ de orden al menos 3 es no-separable si y sólo si cualquier par de elementos de $G$ están en un ciclo común.
	
	\item Considera una gráfica $G$ de orden $n\geq 3$ que satisfaga que para cualquier par de vértices no adyacentes $u$ y $v$, $\text{d}_{G}(u)+\text{d}_{G}(v) \geq n$. Prueba que $G$ es no-separable.
	
	\item 
	\begin{enumerate}
	  \item Sea $R$ una relación definida sobre el conjunto de aristas de una gráfica conexa $G$ no trivial. Para $e$, $f \in E$, diremos que $eRf$ si $e=f$ o $e$ y $f$ están en un ciclo común. Prueba que $R$ es de equivalencia. ¿Cuáles son las clases de equivalencia inducidas por $R$?
	  \item Sean $B_{1}$ y $B_{2}$ bloques de una gráfica conexa $G$ no trivial, pruebe que se cumplen las siguientes propiedades:
	  \begin{enumerate}
	  \item $B_{1}$ y $B_{2}$ son ajenos por aristas.
	  \item $B_{1}$ y $B_{2}$ tienen a lo más un vértice común.
	  \item Si $B_{1}$ y $B_{2}$ tienen un vértice común $v$ entonces $v$ es de corte en $G$.
	  \end{enumerate}
	  
  \item Demuestra que la gráfica de bloques y de vértices de corte de una gráfica conexa $G$, es un árbol.	  

	\end{enumerate}
	
	
	\item
\begin{enumerate}	
	\item Encuentra todos los árboles $T$ tales que su complemento también es un árbol.
  \item Prueba que todo árbol no trivial es bipartito.
\end{enumerate}
	
	\item Considera $T$ un árbol con $V_1$ el conjunto de hojas de $T$ y $V_3$ el conjunto de vértices de grado mayor o igual que dos de $T$. Prueba que:
\begin{displaymath}
 \lvert V_1 \rvert = \sum_{v \in V_3} d(v) -2 \lvert V_3 \rvert +2\text{.}
\end{displaymath}

 
  \item Dado $T$ cualqueir árbol de orden $k+1$. Prueba que si una gráfica $G$ satisface que $\delta(G) \geq k$ entonces $G$ tiene una subgráfica que es isomorfa a $T$ (\textit{Sugerencia.} Usa inducción).
  
  \item Un árbol generador de una gráfica $G$ es una subgráfica generadora de $G$ tal que es un árbol. Demuestra que toda gráfica conexa posee un árbol generador (\textit{Sugerencia.} Usa inducción).
	
	
	
\end{enumerate}


\end{document}