\documentclass[letterpaper, 10pt]{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}

\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{3cm}
\addtolength{\textwidth}{2.5cm}
\addtolength{\hoffset}{-1cm}
% \addtolength{\textwidth}{2cm}

\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}
\DeclareMathOperator{\exc}{e}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\rad}{rad}


\begin{document}
\header{Teoría de las Gráficas II}{Primera lista de ejercicios}

\begin{definicion}
 Dos gráficas $G$ y $H$ son \emph{isomorfas} (y se denota por $G \cong H$) si y sólo si existen biyecciones $\phi:V(G) \to V(H)$ y $\psi:E(G) \to V(G)$ tales que si $uv$ es una arista de $G$ entonces $\psi(uv)=\phi(u)\phi(v)$.
\end{definicion}

\begin{enumerate}
\item \begin{enumerate}
 \item Muestra que si $G \cong H$ entonces $\lvert V(G) \rvert = \lvert V(H) \rvert$ y $\lvert E(G) \rvert = \lvert E(H) \rvert$.
 \item Muestra que el recíproco es falso.
\end{enumerate}
\item Muestra que dos gráficas $G$ y $H$ son isomorfas si y sólo si existe una biyección $\phi:V(G) \to V(H)$ tal que $uv \in E(G)$ si y sólo si $\phi(u)\phi(v) \in E(H)$.
\item Dada $G$ una gráfica, $\lvert E(G)\rvert =\binom{\lvert V(G) \rvert}{2}$ si y sólo si $G$ es completa.
\item \begin{enumerate}
 \item $E(K_{m,n})=mn$;
 \item si $G$ es simple y bipartita entonces $\lvert E(G) \rvert \leq \frac{\lvert V(G)\rvert}{4}$.
\end{enumerate}
\item (***) Una \emph{gráfica $k$-partita} es aquella en la que su conjunto de
vértices se puede partir en $k$ subconjuntos de tal forma que ninguna de sus
aristas tenga ambos extremos en uno de tales subconjuntos; una \emph{gráfica
$k$-partita completa} es aquella en la que cada vértice está unido con todos los
vértices que no están en su mismo subconjunto.  La gráfica completa $m$-partita
con $n$ vértices en la que cada parte tiene $\lceil \frac{n}{m}\rceil$ o
$\lfloor\frac{n}{m}\rfloor$ vertices se denota por $T_{m,n}$.  Muestra que:
\begin{enumerate}
\item $E(T_{m,n})=\binom{n-k}{2}+(m-1)\binom{k+1}{2}$, donde $k=\lfloor \frac{n}{m} \rfloor$;
\item si $G$ es una gráfica completa $m$-partita con $n$ vértices entonces $\lvert E(G) \rvert \leq \lvert E (T_{m,n} \rvert$, la igualdad se dada sólo si $G \cong T_{m,n}$.
\end{enumerate}
\item (*) El $k$-cubo es la gráfica cuyo conjunto de vértices son las $k$-adas
de ceros y unos, dos vértices son adyacentes si y sólo si difieren en
exactamente una coordenada.  Muestra que el $k$-cubo posee $2^k$ vértices,
$k2^{k-1}$ aristas y es bipartita.
\item \begin{enumerate}
\item El \emph{complemento} $G^c$ de una gráfica $G$ es la gráfica cuyo conjunto de vértices es $V(G)$ y dos vértices son adyacentes en $G^c$ si y sólo si no son adyacentes en $G$.  Describe las gráficas $K^c_n$ y $K^c_{m,n}$.
\item (*) Una gráfica $G$ es \emph{autocomplementaria} si $G \cong G^c$.  Muestra que si $G$ es autocomplementaria entonces $\lvert V(G) \rvert \cong 0$, $1 \pmod 4$.
\end{enumerate}
\item Muestra que toda gráfica con $n$ vértices es isomorfa a una subgráfica de $K_n$.
\item Muestra que:
\begin{enumerate}
 \item toda subgráfica inducida de una gráfica completa es completa y
 \item toda subgráfica de una gráfica bipartita es bipartita.
\end{enumerate}
\item (***) Dada $G$ una gráfica y $n$ un entero con $1 < n < \lvert V(G) \rvert
-1$. Muestra que si $\lvert V(G) \rvert \geq 4$ y todas las subgráficas
inducidas de $G$ con $n$ vértices tienen el mismo número de aristas entonces
$G\cong K_{\lvert V(G) \rvert}$ o $G \cong K^c_{\lvert V(G) \rvert}$.
\item Muestra que $\delta \leq 2\frac{\lvert E(G) \rvert}{\lvert V(G) \rvert} \leq \Delta$.
\item Muestra que si una gráfica bipartita $k$-regular con $k >0$ tiene bipartición $(X$, $Y)$ entonces $\lvert X \rvert =\lvert Y \rvert$.
\item Muestra que, en cualquier grupo de dos o más personas, siempre hay
exactamente dos personas con el mismo número de personas en el grupo.
\item Prueba que si $G$ es una gráfica $k$-regular entonces $r \leq \frac{\lvert
V(G) \rvert}{2}$.
\item (*) Muestra que una gráfica $G$ contiene una subgráfica bipartita
generadora $H$ tal que $d_H(v)\geq \frac{1}{2}d_G(v)$ para todo $v \in V(G)$.
\item ¿Existe una gráfica bipartita $G$ tal que $\delta + \Delta > \lvert V(G)
\rvert$?
\item (*) \begin{enumerate}
       \item Prueba que toda gráfica con $n$ vértices con más de
$\frac{n^2}{4}$ aristas no es bipartita.
       \item Encuentra una gráfica bipartita con $n$ vértices con
$\frac{n^2}{4}$ aristas.
      \end{enumerate}
\item (*) Caracteriza las gráficas bipartitas con la siguiente propiedad: para
cada par de vértices no adyacentes existe un vértice adyacente a ambos.
\item Prueba que si las gráficas $G$ y $H$ son isomorfas entonces $G^c$ y $H^c$
son isomorfas.
\item Da un ejemplo (si es posible) de: \begin{enumerate}
                                         \item una gráfica bipartita
$k$-regular de orden $n$;
                                         \item una gráfica cúbica de orden nueve
                                         \item una gráfica con $n$ vértices y
$\binom{n-1}{2}$ aristas.
                                        \end{enumerate}
\item (*) Encuentra el número de gráficas $(n-2)$-regulares de orden $n$ no
isomorfas entre sí.
\item Encuentra ciclos de longitudes cinco, seis, ocho y nueve en la gráfica de
Petersen.
\item El \emph{cuello} es la longitud del ciclo más chico en una gráfica. 
Encuentra el valor del cuello en $K_n$, $K_{p,q}$ y en la gráfica de Petersen.
\item (*) \begin{enumerate}
       \item Prueba que todo $(u$, $v)$-camino abierto contiene una $(u$,
$v)$-trayectoria.  ¿Será cierto que todo camino cerrado posee un ciclo?
       \item ¿Es cierto que todo $(u$, $v)$-camino que pasa por un vértice $w$
distinto de $u$ o $v$ contiene una $(u$, $v)$-trayectoria que pasa por $w$?
       \item Prueba que todo camino cerrado de longitud impar posee un ciclo. 
¿Es cierta la afirmación para caminos cerrados de longitud par?
       \item Prueba que todo paseo cerrado posee un ciclo.
      \end{enumerate}
\item (*) Prueba que en cualquier gráfica $G$ la distancia $d(u$, $v)$ para $u$,
$v$ vértices de $G$, es una métrica (\textit{i.e.}, satisface los axiomas de una
métrica):
\begin{enumerate}
 \item $d(u$, $v)\geq 0$,
 \item $d(u$, $v)=0$ si y sólo si $u=v$,
 \item $d(u$, $v)=d(v$, $u)$ y
 \item $d(u$, $v)+d(v$, $w) \geq d(u$, $w)$ (Desigualdad del triángulo).
\end{enumerate}
\item Prueba que una gráfica $G$ es conexa si y sólo si
\begin{enumerate}
 \item dado un vértice fijo $u$, existen $(u$, $v)$-trayectorias en $G$ para
cualquier otro vértice $v$ en $G$,
 \item para toda partición de los vértices de $G$ (\textit{i.e.}, $V_1$, $V_2
\subseteq V(G)$ tales que $V(G)=V_1 \cup V_2$, $V_1 \cap V_2=\emptyset$ y $V_i
\neq \emptyset$ para $i=1$, $2$) existe una arista $(u$, $v)$ de $G$ tal que $u
\in V_1$ y $v \in V_2$.
\end{enumerate}
\item Prueba que si una gráfica posee exactamente dos vértices de grado impar
entonces están conectados por una trayectoria.
\item (*) Prueba que si el grado mínimo de una gráfica es mayor que uno entonces
posee un ciclo.
\item (*) \begin{enumerate}
       \item Prueba que una gráfica es bipartita si y sólo si no posee ciclos
de longitud impar.
       \item Prueba que la bipartición de una gráfica bipartita conexa es
única. ¿Es cierto para gráficas disconexas?
      \end{enumerate}
\item Encuentra todas las gráficas bipartitas cuyos complementos también son
bipartitas.  Encuentra la autocomplementaria.
\item Encuentra todas las gráficas bipartitas de diámetro dos.
\item (*) Prueba que para todo entero $r >1$ existe una gráfica $r$-regular de
orden $2r$ y diámetro $2$.
\item (**) Describe la estructura de una gráfica conexa $G$ que satisface una de las
condiciones siguientes:
\begin{enumerate}
 \item la longitud de cualquier trayectoria maximal con respecto a la inclusión
es $2$,
 \item para cualquier vértice $v$ de $G$, todos los vértices de su vecindad
son adyacentes dos a dos,
 \item todo vértice tiene grado uno,
 \item toda arista incide en un vértice de grado uno,
 \item todas las aristas son dos a dos adyacentes,
 \item el número de aristas es igual al número de vértices de grado uno,
 \item $\delta(G)=1$ y $\Delta(G)=2$ o
 \item $G$ es isomorfa a su gráfica de líneas.
\end{enumerate}
\item (*) Prueba que si borras cualquier arista en un ciclo de una gráfica conexa,
obtienes una gráfica conexa.
\item (*) ¿Cuál es el mínimo número de aristas en una gráfica conexa con $n$
vértices?
\item Prueba que para cualesquiera dos aristas $e_1$ y $e_2$ en una gráfica
conexa existe una trayectoria cuya primera arista es $e_1$ y cuya última arista
es $e_2$.
\item (*) \begin{enumerate}
 \item Prueba que una gráfica $G$ de orden $n$ es conexa si $\delta(G) \geq
\frac{n-1}{2}$.  ¿La afirmación sigue siendo cierta si reemplazamos
$\frac{n-1}{2}$ por $\lfloor \frac{n-1}{2} \rfloor$?
 \item Prueba que una gráfica $G$ de orden $n > 2$ es conexa si el número de
aristas es mayor que $\frac{n-1}{2}$.  ¿Podemos reemplazar ``mayor'' por ``no
menor''?
 \item Prueba que una gráfica $G$ de orden $n$ y tamaño $m$ es conexa si no
posee ciclos de longitud impar y $m > (\frac{n-1}{2})^2$?  ¿Sigue siendo cierto
si reemplazamos $>$ por $\geq$?
\end{enumerate}

Recuerda que la \emph{excentricidad} de un vértice $u$ en $G$ es la máxima de
las distancia a todos los otros vértices de $G$, es decir, $\exc(u)=\max_{v \in
V(G)} d(u$, $v)$.

La máxima entre las excentricidades de todos los vértices es
el \emph{diámetro} de la gráfica y se denota por $\diam(G)$.  Si para algún
vértice $v$ en $G$ se tiene que $\exc(v)=\diam(G)$ entonces se dice que es
\emph{periférico}.

La mínima entre las excentricidades de todos los vértices es el \emph{radio} de
la gráfica y se denota por $\rad(G)$.  Si para algún vértice $v$ en $G$ se tien
que $\exc(v)=\rad(G)$ entonces se dice que es \emph{central}.  La subgráfica de
$G$ inducida por sus vértices centrales es el \emph{centro} de $G$.

\item (*) Prueba que: \begin{enumerate}
                       \item el diámetro de una gráfica es a lo más dos veces
su radio y
                       \item una trayectoria cuya longitud sea la del diámetro
pasa por un vértice central.
                      \end{enumerate}
\item (*) Para todo $n \geq 4$  da una ejemplo de una gráfica de orden $n$
distinta de la completa que satisfaga que: \begin{enumerate}
                                   \item su radio y su diámetro sean iguales,
                                   \item todos sus vértices son periféricos y
                                   \item todos sus vértices son centrales.
                                  \end{enumerate}
\item (*) Prueba que:\begin{enumerate}
                  \item para cualquier gráfica $G$, ella o su complemento son
conexas,
 \item si $G$ no es conexa entonces el diámetro de su complemento es menor o
igual que dos,
 \item si $G$ y su complemento son conexas y $\diam(G) \geq 3$ entonces el
diámetro del complemento es menor o igual que tres.
 \item $1 \leq \diam(G) \leq 3$ para cualquier gráfica autocomplementaria no
trivial $G$.
                 \end{enumerate}
\item (*) Prueba que si una gráfica no tiene triángulos entonces $\delta(G) +
\Delta(G) \leq \lvert V(G) \rvert$.
\item (*) La \emph{representación de König} de una gráfica $G$ es la gráfica
bipartita $K(G)$ en la que una de sus partes son los vértices de $G$ y la otra
las aristas de $G$.  Dos vértices en $K(G)$ son adyacentes si y sólo si el
vértice y la aristas correspondientes en $G$ son incidentes.  Prueba que
\begin{enumerate}
 \item $K(G)$ puede ser obtenida de $G$ mediante \emph{subdivisiones} de sus
aristas, \textit{i.e.}, para cada arista $(u$, $v)$ en $G$, añadimos un nuevo
vértice $w_{uv}$ y la arista la reemplazamos por dos aristas $(u$, $w_{uv})$ y
$(w_{uv}$, $v)$.
 \item Dos gráficas son isomorfas si y sólo si sus representaciones de König lo
son.
\end{enumerate}
\item Prueba que:
 \begin{enumerate}
 \item la subgráfica de un subgráfica de una gráfica de $G$ es subgráfica de
$G$,
 \item la subgráfica generadora de una subgráfica generadora de $G$ es
subgráfica generadora de $G$ y
 \item una subgráfica inducida de una subgráfica inducidad de $G$ es subgráfica
inducida de $G$.
 \end{enumerate}
\item (*) Prueba que:
 \begin{enumerate}
 \item cualquier subgráfica de una gráfica $G$ se puede obtener al borrar
algunos vértices o aristas de $G$,
 \item cualquier subgráfica generadora de una gráfica $G$ se puede obtener al
borrar algunas aristas de $G$ y 
 \item cualquier subgráfica inducida de una gráfica $G$ se puede obtener al
borrar algunos vértices de $G$.
 \end{enumerate}
\item Supón que $G$ y $H$ son gráficas tales que $V(G)=V(H)$ y $d_G(v) \geq
d_H(v)$ para todo vértice $v$.  ¿Es cierto que $H$ es subgráfica de $G$?
\item ¿Es cierto que $\delta(G) \leq \delta (H)$ si $H$ es
 \begin{enumerate}
 \item una subgráfica de $G$?
 \item una subgráfica generadora de $G$?
 \end{enumerate}
\item ¿Cuál es la estructura de una gráfica en la que toda trayectoria es una
subgráfica inducida?
\item (*) Prueba que para cualquier gráfica $G$ existe una gráfica
autocomplementaria que posee a $G$ como subgráfica inducida.
\item (*) ¿Será cierto que el conjunto los vértices de cualquir gráfica $G$
puede ser partido en dos conjuntos $V_1$ y $V_2$ de forma tal que las
subgráficas inducidas por $V_1$ y $V_2$ sean regulares?
\item (*) Prueba que no existen gráficas de orden $n \geq 5$ tales que
cualesquiera cuatro vértices inducen un ciclo de longitud cuatro.
\item (*) Prueba que toda gráfica $G$ es una subgráfica inducida de alguna
gráfica $\Delta(G)$-regular.
\item (*) Caracteriza todas las gráficas en las que los conjuntos $N(v)$
inducen gráficas completas para todos los vértices $v$.
\item (*) Encuentra una gráfica de orden diez en la que las vecindades de todos
los vértices inducen la gráfica $P_2^c$ donde $P_2$ es la trayectoria de
longitud dos.
\item (*) Encuentra todas las gráficas conexas en las que los conjuntos $N(v)$
para cualquier vértice $v$ induce la gráfica:
 \begin{enumerate}
 \item un ciclo de longitud tres y
 \item un ciclo de longitud cuatro.
 \end{enumerate}
\item (*) Prueba que una gráfica acíclica con $n$ vértices y $k$ componentes posee exactamente $n-k$ aristas.
\item (*) El \emph{grado promedio} de una gráfica de orden $n$ es el valor $d(G)=\frac{1}{n}\sum_{v\in V(G)} d_G(v)$.  Expresa el número de vértices de un árbol en término del grado promedio.
\item (*) Prueba que para cualquier árbol no trivial:
 \begin{enumerate}
 \item posee al menos dos vértices de grado uno y
 \item posee exactamente dos vértices de grado uno y sólo si el árbol es una trayectoria.
\end{enumerate}
\item (*) Encuentra todos los árboles en los que el diámetro sea igual a su radio.
\item (*) Prueba que, si $T$ es un árbol, su radio y su diámetro tienen la relación:
\begin{displaymath}
 \rad(T)=\lceil \frac{\diam(T)}{2}\rceil\text{.}
\end{displaymath}
\item (*) Construye gráficas $2$-conexas de orden $n$ con $\diam(G)=2$ y $\lvert E(G) \rvert = 2n-5$ para todo $n \geq 5$.
\item (*) Si $v$ es un vértice de corte en una gráfica $G$ entonces $v$ no es de corte en $G^c$.
\end{enumerate}
\end{document}