\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{wrapfig} 
% \usepackage{pdfsync}
% \usepackage{floatflt}
% \usepackage{makeidx}
% \usepackage{ifpdf}
% \usepackage{graphfig}
% \usepackage{subfig}
\usepackage{graphics} 
\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}
% \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{wrapfig} 
% % \usepackage{pdfsync}
% % \usepackage{floatflt}
% % \usepackage{makeidx}
% % \usepackage{ifpdf}
% % \usepackage{graphfig}
% % \usepackage{subfig}
% \usepackage{graphics} 
% \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}{Tercera tarea\\Primero de octubre de 2010}

\begin{enumerate}
\item Considera una gráfica $G$ conexa.
\begin{enumerate}
 \item Muestra que si $x$ es una vértice de grado uno entonces $G-x$ es conexa.
 \item Muestra que si $G$ es una gráfica conexa de orden $n \geq 2$ entonces debe poseer al menos $n-1$ aristas. ¿Qué puedes decir del recíproco?
\end{enumerate}
 \item Considera $G$ una gráfica de orden $n$. Muestra que si el tamaño de $G$ es estrictamente mayor que $(n-1)(n-2)/2$ entonces $G$ es conexa.
 \item Considera $G$ una gráfica de orden $n$ con $\omega$ componentes conexas. Muestra que el tamaño de cada componente es a lo más $(n-\omega)(n-\omega+1)/2$.
 \item Considera la gráfica que aparecen en la figura~\ref{fig1}. ¿Cuántos ciclos posee? ¿Cuántas trayectorias de longitud cinco posee? Enumera todas sus trayectorias que tengan por extremos los vértices $x$ y $y$.
\begin{figure}[hb]
  \centering
  \includegraphics{dibujo1}
  \label{fig1}
  \caption{Gráfica}
\end{figure}
 \item Prueba que si un camino $C$ en una gráfica $G$ no repite vértices entonces no repite aristas.
 \item  Si $C$ y $C'$ son caminos y su concatenación existe entonces $l(C)+l(C')=l(C\bullet C')$.
 \item Dado un camino $C=(x_0$, $x_1$, \ldots, $x_k)$ y $x_i$ un vértice interior de $C$ entonces:
\begin{itemize}
 \item $C[x_0$, $x_i]\bullet C[x_i$, $x_k]=C$
 \item $l(C[x_0$, $x_i])+l(C[x_i$, $x_k])=l(C)$
\end{itemize}
 \item ¿Cómo se ven todos los posibles caminos de longitud tres y cuatro? (Considera $K_3$ y $K_4$ y toma en cada uno caminos de longitud tres y cuatro, respectivamente, considerando que las aristas y los vértices pueden repetirse ninguna o algunas veces).
	\item Sea $A$ la matriz de adyacencia de una gráfica $G$, con $V(G)=\{v_{1},v_{2},\dots ,v_{n}\}$. $A^1:=A$ y $A^i:=A^{i-1}A$ (con la multiplicación usual de matrices). Prueba que la entrada $(i,j)$ de $A^{k}$, $k\geq 1$, es el múmero de diferentes $(v_{i}$, $v_{j})$-caminos de longitud $k$ en $G$.
		\item Sean $u$ y $v$ cualesquiera dos vértices de una gráfica conexa $G$. Muestra que existe un $(u$, $v)$-camino \emph{abierto} que contiene todos los vértices de $G$.
	
	\item Sea $G$ una gráfica de orden $n$ tal que $\delta_{G}(v)\geq \frac{n-1}{2}$ para todo $v\in V(G)$. Muestra que G es conexa.
	
% 	\item Sea $n\in \mathbb{Z}^{+}$, $n\geq2$. Determina el mínimo entero positivo $m$ tal que toda gráfica de orden $n$ y tamaño $m$ es conexa. Justifica tu respuesta.
	

% 	\item Prueba que una gráfica $G$ es conexa si y sólo si para toda partición de $V(G)$ en dos conjuntos $V(G)=V_{1}\cup V_{2}$ existe una $V_{1}V_{2}$-arista en $G$.
% 	
	\item Prueba que toda gráfica $G$ contiene una trayectoria de longitud al menos $\delta(G)$.
	
	\item Caracteriza todas aquellas gráficas $G$ con la propiedad de que toda subgráfica inducida de $G$ es una subgráfica conexa de $G$.
	
	\item Sea $G$ una gráfica con $A(G)\neq \emptyset$, conexa y no bipartita. Muestra que $G$ tiene vértices $u$ y $v$ no adyacentes tales que $\delta_{G}(u)+\delta_{G}(v)$ es par.
	
	\item Prueba que si $G$ es disconexa entonces $\overline{G}$ es conexa y, además, $\mathrm{diam}(G)\leq 2$.
	
	\item Prueba que $G$ es bipartita si y sólo si toda componente conexa de $G$ es bipartita.
\end{enumerate}

\section*{Extras}
\begin{enumerate}
	\item Sea $G$ una gráfica de orden $n$ y tamaño $m$. Muestre que $G$ tiene al menos $m-n+\omega$ ciclos distintos. Donde $\omega$ es el número de componentes conexas de $G$.
	
	\item Sea $G$ una gráfica conexa. Muestra que:
	
\begin{enumerate}
	\item Si $u$ y $v$ son vértices adyacentes de $G$, entonces $\left|e(u)-e(v)\right| \leq 1$.
	\item Si $k$ es un entero tal que $\mathrm{rad}(G)\leq k \leq \mathrm{diam}(G)$, entonces existe un vértice $w$ tal que  $e(w)=k$.
	\item Si $k$ es un entero tal que $\mathrm{rad}(G)<k\leq \mathrm{diam}(G)$, entonces existen al menos dos vértices en $G$ con   excentricidad $k$.\\
	$\longrightarrow$ Sugerencia: Sea $w$ un vértice con $e(w)=k$, y sea $u$ un vértice tal que $d(w,u)=e(w)=k$. Sea $v$ un   vértice central de $G$ y $T$ una $vu$-trayectoria de longitud $d(v,u)$. Muestra que $e(v)<k\leq e(u)$. Concluye que existe un  vértice $x\neq w$ en $T$, tal que $e(x)=k$. 
\end{enumerate}
  
\end{enumerate}

\end{document}