\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}{Quinta lista de ejercicios \\11 de noviembre de 2011}

\begin{enumerate}
	\item ¿Cuál es el número máximo de vértices de corte que puede tener una gráfica con $n$ vértices?
	\item Sea $e$ una arista de una gráfica conexa $G$. Pruebe que los siguientes enunciados son equivalentes:
	
\begin{enumerate}
	\item $e$ es un puente de $G$.
	\item $e$ no está en ningún ciclo de $G$.
	\item Existen vértices $u$ y $v$ en $G$, tales que toda $uv$-trayectoria pasa por $e$.
	\item Existe una partición de $V(G)$ en dos conjuntos $U$ y $W$, tal que toda $UW$-trayectoria pasa por $e$.
\end{enumerate}

	\item Prueba que si $G$ tiene un puente, entonces tiene un vértice de corte y muestre que el recíproco no necesariamente se cumple.
	\item Demuestra que si $v$ es un vértice de corte en $G$, entonces $v$ no es de corte en $G^{c}$.
	\item Demuestra o da un contraejemplo: Una gráfica conexa $G$ con al menos tres vértices, es un bloque si y sólo si para cualesquiera dos vértices $u$ y $v$ y cualquier arista $e$, existe una $uv$-trayectoria que no pasa por $e$.
	\item Sea $G$ una gráfica conexa y $b(v)$ el número se bloques de $G$ que contienen al vértice $v$. Prueba que el número de bloques de $G$ es $$1+\sum_{v\in V(G)}(b(v)-1)$$
	\item
\begin{enumerate}
	\item Encuentra una gráfica $G$ tal que $\kappa(G)=3$, $\lambda(G)=4$ y $\delta(G)=5$.
	\item Prueba que no existe una gráfica $3$-conexa de tamaño $7$.
\end{enumerate}
  	
	\item Una arista $uv$ es la diagonal de un ciclo $\gamma$ en $G$ si $\{u,v\}\subset V(\gamma)$ y $uv\notin E(\gamma)$. Prueba que una arista $e$ de una gráfica $2$-conexa es diagonal de un ciclo en $G$ si y sólo si $G-e$ es $2$-conexa.
	\item Sea $G$ una gráfica y sean $w\in V(G)$ y $e\in E(G)$, prueba que $\forall u,v\in V(G)$, $u\neq v$ y $u\ \text{no ady}_{G}\ v$ se tiene que:
	
\begin{enumerate}
	\item $\kappa_{G-w}(u,v)=\left\{ \begin{aligned} &\kappa_{G}(u,v)\ \text{ó} \\ &\kappa_{G}(u,v)-1 \end{aligned} \right.$
	\item $\kappa_{G-e}(u,v)=\left\{ \begin{aligned} &\kappa_{G}(u,v)\ \text{ó} \\ &\kappa_{G}(u,v)-1 \end{aligned} \right.$
\end{enumerate}
Concluye que para cualquier arista $x$ de $G$: $$\kappa_{G-x}(G)= \left\{ \begin{aligned} &\kappa_{G}(u,v)\ \text{ó} \\ &\kappa_{G}(u,v)-1 \end{aligned} \right.$$

  \item Prueba que una gráfica $G$ es $k$-conexa si y sólo si $\forall u,v\in V(G)$ existen al menos $k$ $uv$-trayectorias internamente ajenas.
  \item Prueba que si $G$ es $k$-conexa con $k\geq 2$, entonces para cualquier conjunto $S\subset V(G)$ de cardinalidad $k$ existe un ciclo $\gamma$ tal que $S\subset V(\gamma)$.

\end{enumerate}

\textbf{Extras:}

\begin{enumerate}
	\item Prueba que si $T$ es un árbol tal que la distancia entre cualesquiera dos de sus vértices terminales es par, entonces $T$ es la gráfica de bloques y de vértices de corte de alguna gráfica $G$.
	\item Muestra que $\kappa(Q_{n})=\lambda(Q_{n})=n$, para toda $n\in \mathbb{Z}^{+}$.
	\item Sea $G$ una gráfica $k$-conexa y sea $v\in V(G)$. Para todo $t\in \mathbb{Z}^{+}$, definimos $G_{t}$ como la gráfica obtenida de $G$ al añadir $t$ nuevos vértices, $u_{1},u_{2},\dots,u_{t}$ y todas las aristas de la forma $u_{i}w$, con $1\leq i \leq t$ y para cada $vw\in E(G)$. Prueba que $G_{t}$ es $k$-conexa.  
\end{enumerate}


\end{document}