\documentclass[letterpaper, 12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{palatino}
\usepackage{latexsym,amssymb,amsfonts,amsmath}
\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{paralist}
\usepackage{graphics}
\usepackage[all]{xy}
\pagestyle{empty}
 
\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}

\begin{document}
\header{Teoría de las Gráficas}{Décima (y última) tarea\\10 de junio de 2009}

\emph{Tarea preliminar.  Faltan los ejercicios dejados en clase (supón que son $n$).  De esta tarea, responde $10-n$.  Más, no contarán (excepto, obvio, el extra.)}

Una gráfica dibujada en el plano es una \emph{representación} de la gráfica.  Las Figuras~\ref{fig:K4a} y~\ref{fig:K4b} son dos representaciones distintas en el plano de $K_4$.  Aquélla tiene un cruce mientras ésta no.  El \emph{número de cruces} de una representación es el número de pares diferentes de aristas que se intersecan; el número de cruce $\nu(G)$ de una gráfica $G$ es el mínimo de los números de cruces de todas las representaciones de $G$ en el plano.  Así, una representación es \emph{plana} si no tiene cruces.  En otras palabras, una gráfica $G$ es \emph{plana} si $\nu(G)=0$.  La Figura~\ref{fig:K4b} muestra que $K_4$ es plana.
\begin{figure}[!h]
	\begin{displaymath}
	\xygraph{
	!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
	!{(0,0) }*{\bullet}="1"
	!{(0,1) }*{\bullet}="2"
	!{(1,0) }*{\bullet}="3"
	!{(1,1) }*{\bullet}="4"
	"1"-"2" "2"-"3" "3"-"4" "4"-"1" "1"-"3"
	"2"-"4"
	}
	\end{displaymath}
	\caption{Una representación en el plano de $K_4$}
	\label{fig:K4a}
\end{figure}
\begin{figure}[!h]
	\begin{displaymath}
	\xygraph{
	!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
	!{(0,0) }*{\bullet}="1"
	!{(1.2,0) }*{\bullet}="2"
	!{(0.6,1.2) }*{\bullet}="3"
	!{(0.6,0.5) }*{\bullet}="4"
	"1"-"2" "2"-"3" "3"-"4" "4"-"1" "1"-"3"
	"2"-"4"
	}
	\end{displaymath}
	\caption{Otra representación en el plano de $K_4$}
	\label{fig:K4b}
\end{figure}

Supón que $G$ es plana.  Si construimos una nueva gráfica insertando un nuevo vértice de grado dos ``en medio'' de una arista (\emph{división de una arista}) o borrando un vértice de grado dos y uniendo sus dos vértices adyacentes (\emph{elidir un vértice}), esa nueva gráfica también será plana.  Gráficas que pueden ser obtenidas de otra por estas operaciones se llaman \emph{homeomorfas}.

Ya que $K_5$ y $K_{3,3}$ no son planas, se sigue que una gráfica que tiene una de ellas como subgráfica no puede ser plana.  Más aún, una gráfica que es homeomórfica a una que posea una \emph{subgráfica} homeomórfica a $K_5$ ó $K_{3,3}$ no puede ser plana.  Kuratowski probó que esta condición necesaria para la planaridad también es necesaria.

\begin{teorema}[Kuratowski, 1930]
\label{Kur}
 $G$ es plana si y sólo $G$ es homeomórfica a una gráfica que no tiene subgráficas homeomórficas a $K_5$ ó $K_{3,3}$.
\end{teorema}

\begin{teorema}
\label{plana}
 Si una gráfica plana conexa tiene $p$ vértices y $q$ aristas, con $p \geq 3$, entonces $q \leq 3p-6$.
\end{teorema}

Decimos que una gráfica $G$ es \emph{crítica} si y sólo si para cualquier subgráfica $H$ de $G$, $\chi(H) < \chi(G)$.  Así, una gráfica $G$ es \emph{$k$-crítica} si $G$ es $k$-cromática y crítica.


\begin{enumerate}[1.]
 \item Considera la gráfica bipartita completa $K_{m,n}$.  En una sistema coordenado cartesiano, escoge $\lfloor\frac{m}{2}\rfloor$ puntos en el eje x positivo, $\lceil\frac{m}{2}\rceil$ puntos en el eje x negativo y $\lfloor\frac{n}{2}\rfloor$ puntos en el eje y positivo, $\lceil\frac{n}{2}\rceil$ puntos en el eje y negativo.  La figura formada de unir todos los pares con algún punto en el eje x y algún punto en el eje x es una representación de $K_{m,n}$.  Usa esta representación para probar que
\begin{displaymath}
 \nu(K_{m,n})\leq\bigg\lfloor\frac{m}{2}\bigg\rfloor\bigg\lfloor\frac{m-1}{2}\bigg\rfloor\bigg\lfloor\frac{n}{2}\bigg\rfloor\bigg\lfloor\frac{n-1}{2}\bigg\rfloor
\end{displaymath}
 \item Prueba que la gráfica de Petersen no es plana usando el Teorema~\ref{Kur}.
 \item Dibuja $K_6$ con tres cruces.
 \item ¿Cuánto vale $\nu(K_{3,4})$?
 \item Supón que $G$ es una gráfica con $p$ vértices y $q$ aristas y supón que $\delta(G) \geq 6$.  Prueba que
\begin{displaymath}
 q \geq 3p\text{.}
\end{displaymath}
De aquí que todo gráfica plana contiene al menos un vértice de grado cinco.  (\emph{Sugerencia.\hyphenation{Su-ge-ren-cia}}  Utiliza el Teorema~\ref{plana}.)
 \item Prueba que toda gráfica posee una subgráfica $k$-crítica.
 \item Prueba que para toda gráfica $G$, si es $k$-crítica entonces $\delta(G)\geq k-1$.  (\emph{Sugerencia.}  Por contradicción.)
 \item Prueba usando lo que hay en esta tarea que toda gráfica plana es $6$-coloreable
 \item Prueba que si cualesquiera dos ciclos de longitud impar tienen un vértice en común en $G$ entonces $G$ puede colorearse con a lo más cinco colores.
 \item Si $G$ es una gráfica con exactamente un ciclo de longitud impar entonces $\chi(G) = 3$.
 \item Si $P$ es la gráfica de Petersen, ¿cuánto vale $\chi(P)$?  ¡Argumenta porque no vale menos!
 \item Prueba que
\begin{displaymath}
 \lvert V(G) \rvert \leq \beta(G)\cdot\chi (G)\text{.}
\end{displaymath}
 \item Si $x$ es un vértice de $G$ de grado menor que $n$, muestra que $G$ es $n$-coloreable si y sólo si $G-x$ lo es.
\end{enumerate}

\begin{enumerate}
 \item [Extra.]  Prueba que las únicas gráficas $3$-críticas son los ciclos de longitud impar.
\end{enumerate}

\end{document}