Grafos

I.T.I. GESTIO´ N MATEMA´ TICA DISCRETA BOLET´IN CON LOS EJERCICIOS RESUELTOS




1. Introducci´on a la teor´ıa de grafos


1. a) ¿Cu´antas aristas tiene Kn ?
b) ¿Cu´antas aristas tiene Km,n ?
Soluci´on.

a) Con generalidad, ocurre enteor´ıa de grafos que un mismo problema se puede resolver de varias formas distintas, algunas m´as cortas que otras, algunas m´as elegantes que otras. Aunque basta resolver el problema por uno de entre los m´etodos disponibles, siempre es enriquecedor plantearse alternativas distintas para resolver un mismo problema. En el caso que nos lleva, el nu´mero de
n(n − 1)aristas de Kn es a =
, cuesti´on que vamos a demostrar de tres formas distintas.
2
a.1) Si tratamos de contar las aristas una a una, resulta que del primer v´ertice, x1 , salen n − 1 aristas; del segundo, x2 , n − 2 que no se hayan contado (todas, salvo la que une x2 con x1 , que se ha contado antes); y, as´ı sucesivamente, del i-´esimo v´ertice, xi , salen n − iaristas que
no se hayan contado antes. De hecho, de xn−1 sale una sola arista que no se haya contado antes, precisamente la que une este v´ertice con xn . Y de xn no hay ninguna arista que salga que no haya sido contemplada con anterioridad. En definitiva, el grafo tiene tantas aristas
como suma la expresi´on a = (n − 1) + (n − 2) + · · · + 1 + 0, progresi´onaritm´etica de paso 1 que se puede hallar sumando los t´erminos extremos dos a dos; de manera que a = n(n − 1) .
2
a.2) Utilizando argumentos de combinatoria, el grafo Kn tiene todas las aristas que caben entre
los n v´ertices. Como una arista es un par no ordenado de v´ertices, Kn consta de todos
los pares no ordenados que se pueden formar con nv´ertices, sin repetir ninguno; esto es,

combinaciones de n elementos tomados de 2 en 2, C2,2 =
µ n ¶ =
2
n(n − 1) .
2
a.3) El grafo completo Kn consiste en un grafo (n − 1)-regular de n v´ertices. Segu´n el lema del
apreton de manos,
n
2a = X δ(xi ) = X(n − 1) = n(n − 1)de donde a = n(n − 1) .
2
xi ∈V
i=1
b) Aunque este apartado se puede resolver tambi´en de varias formas, an´alogas a las anteriores, s´olo mostraremos la u´ltima modalidad, aplicando el lema del apret´on de manos. El grafo Km,n consta de m v´ertices de valencia n y otros n v´ertices de valencia m. De manera que ha de ser





de manera que a = mn.
m
2a = X n +i=1
m+n
X

i=m+1

m = mn + nm = 2mn




2. Demostrar que todo grafo de 3n v´ertices de valencias comprendidas entre n y n + 2 contiene al menos bien n v´ertices de valencia n, bien n + 2 v´ertices de valencia n + 1, bien n + 1 v´ertices de valencia n + 2.
Soluci´on.



Sea un grafo de 3n v´ertices de valencias n, n + 1 o n + 2. Si no tiene al menosbien n v´ertices de valencia n, bien n + 2 v´ertices de valencia n + 1, bien n + 1 v´ertices de valencia n + 2; entonces tiene
a lo m´as n − 1 v´ertices de valencia n, n + 1 v´ertices de valencia n + 1 y n v´ertices de valencia n + 2. Pero como el grafo tiene 3n v´ertices, estas cantidades se alcanzan, de manera que n − 1 de los v´ertices
tienen de hecho valencia n, otros n + 1tienen valencia n + 1 y los restantes n tienen valencia n + 2.
As´ı, la lista de grados es de la forma (n + 2, .n. ., n + 2, n + 1, n.+. .1, n + 1, n, n.−. .1, n). Pero esto es imposible, porque hay un nu´mero impar de v´ertices de valencia impar:

• Si n es par, los v´ertices de valencia impar son aquellos con valencia n + 1, que totalizan n + 1 v´ertices, ¡en cantidad impar!...