Exercicios resolvidos

Prévia do material em texto

Elementos de Matema´tica Finita (2011-2012)
Teoria de Grafos: problemas resolvidos
1 - Verificar se cada uma das listas seguintes pode representar os graus dos
ve´rtices de um grafo (simples) e no caso afirmativo, representar graficamente
um grafo nessas condic¸o˜es:
a) {3, 3, 2, 2, 2, 1}
b) {6, 6, 6, 4, 4, 2, 2}
c) {6, 6, 6, 6, 5, 4, 2, 1}
d) {6, 6, 6, 4, 4, 3, 3}
Resoluc¸a˜o: A sequeˆncia da al´ınea a) na˜o pode representar os graus dos
ve´rtices de um grafo, uma vez que o nu´mero de ve´rtices de grau ı´mpar tem que
ser par e nesta sequeˆncia temos 3 valores ı´mpares.
A sequeˆncia da al´ınea b) tambe´m a˜o pode representar os graus dos ve´rtices de
um grafo simples; para justificar isso basta ver que se assim fosse cada um dos
ve´rtices de grau 6 teria que ser adjacente a todos os outros ve´rtices; logo todos
os ve´rtices teriam grau maior ou igual a 3.
Podemos aplicar um racioc´ınio do mesmo tipo na al´ınea c), mas em vez disso,
podemos usar o facto de que a sequeˆncia e´ a sequeˆncia de graus de um grafo
simples se e so´ se {5, 5, 5, 4, 3, 1, 1} tambe´m o for, se e so´ se {4, 4, 3, 2, 1, 0}e agora
a ideia aplicada em b) aplica-se claramente: cada um dos dois ve´rtices de grau
4 teria que ser adjacente a cada um dos outros treˆs ve´rtices de grau positivo, e
portanto na˜o poderia haver ve´rtices de grau 1.
Finalmente, a u´ltima sequeˆncia e´ a sequeˆncia de graus de um grafo simples:
ligamos os treˆs ve´rtices de grau 6 entre si e a cada um dos outros quatro ve´rtices
e finalmente escolhemos dois destes para serem adjacentes um do outro.
2 - O complemento de um grafo simples G, e´ o grafo G que tem os mesmos
ve´rtices de G mas em que dois ve´rtices sa˜o adjacentes se e so´ se o na˜o forem em
G.
a) Se G tem n ve´rtices com graus d1, d2, · · · , dn quais sa˜o os graus dos ve´rtices
de G?
b) Mostrar que se G e´ desconexo, enta˜o G e´ conexo. A rec´ıproca e´ verdadeira?
Resoluc¸a˜o: a) G tem sequeˆncia de graus (para a mesma ordem de ve´rtices)
n− 1− d1, n− 1− d2, · · · , n− 1− dn
b) Suponhamos que G e´ desconexo e que o conjunto dos ve´rtices V se decompo˜e
como
V = V1 ∪ V2, V1 ∩ V2 = ∅, V1 6= ∅ 6= V2
de modo a que na˜o haja arestas entre V1 e V2.
Enta˜o quaisquer dois ve´rtices u ∈ V1 e v ∈ V2 sa˜djacentes em G; por outro
lado, dados dois ve´rtices x e y de, por exemplo, V1, existe um caminho de
comprimento 2 entre eles passando por cada um dos ve´rtices de V2; e o mesmo
se passa para x, y ∈ V2.
noindent Logo se G e´ na˜o conexo, G e´ conexo.
A rec´ıproca na˜o e´ verdadeira e e´ fa´cil encontrar exemplos. Por exemplo o grafo
G com matriz de adjaceˆncia 
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0

e´ conexo e G tambe´m.
3 - Mostrar que em qualquer grafo existem dois ve´rtices com o mesmo grau.
Sugesta˜o: usar o Princ´ıpio do Pombal.
Resoluc¸a˜o: Se G tem n ve´rtices, os graus destes podem tomar n valores:
0 ≤ d(v) ≤ n − 1. No entanto, se algum ve´rtice tiver grau 0, nenhum pode ter
grau n− 1 e vice-versa. Portanto, os graus dos n ve´rtices so´ podem tomar n− 1
valores e pelo Princ´ıpio do Pombal, dois deles teˆm que ter o mesmo valor.
4 - Um grafo e´ regular de grau k se todos os ve´rtices teˆm grau k. Quantos
grafos de ordem 7 e regulares de grau 4, na˜o isomorfos, e´ que existem? Sugesta˜o:
considerar o complemento do grafo.
Resoluc¸a˜o: Notamos primeiro que dois grafos sa˜o isomorfos se e so´ se os
seus complementares sa˜o isomorfos: de facto, se G tem ve´rtices V e H tem
ve´rtices U , um isomorfismo entre G e H e´ uma bijecc¸a˜o f : V → U tal que
x, y ∈ V sa˜o adjacentes em G⇔ f(x), f(y) ∈ U sa˜o adjacentes em H
e portanto f tambe´m e´ um isomorfismo entre G e H.
O complementar de um grafo com 7 ve´rtices e regular de grau 4 e´ regular de
grau 2 e portanto tem que ser constitu´ıdo por uma unia˜o disjunta de caminhos
fechados (ciclos). So´ ha´ 2 grafos (ou, mais precisamente, duas classes de isomor-
fismo de grafos) nessas condic¸o˜es, um ciclo de comprimento 7 e a unia˜o disjunta
de um ciclo de comprimento 3 com um de comprimento 4. Logo a resposta e´ 2.
Observac¸a˜o: Podemos tentar aplicar o mesmo racioc´ınio para determinar
quantos grafos de ordem n e regulares de grau n − 3, a˜o isomorfos entre si,
existem. O complementar de um desses grafos e´, a` semelhanc¸a do caso anterior,
um grafo de ordem n e regular de ordem 2, logo e´ uma unia˜o disjunta de ciclos,
e duas unio˜es disjuntas de ciclos sa˜o isomorfas se e so´ se, para cada k, o nu´mero
de ciclos de comprimento k em cada uma delas for igual.
O problema reduz-se portanto a determinar quantas partic¸o˜es de n em parcelas
maiores ou iguais a 3 existem. Mas embora possamos calcular esse nu´mero para
cada valor concreto de n, na˜o temos uma fo´rmula fechada.
5 - Seja G um grafo simples com n ve´rtices.
a) Mostrar que se |AG| >
(
n− 1
2
)
, enta˜o G e´ conexo.
b) Dar um exemplo de um grafo desconexo em que |AG| =
(
n− 1
2
)
.
c) Mostrar que se o grau mı´nimo de G satisfaz δ(G) >
n− 2
2
, enta˜o G e´
conexo.
d) Dar um exemplo de um grafo desconexo com δ(G) =
n− 2
2
.
Resoluc¸a˜o: a) Se G na˜o e´ conexo, podemos repartir o conjunto dos ve´rtices
em dois conjuntos V1 e V2, disjuntos e na˜o vazios, um com k ve´rtices e o outro
com n−k, onde 1 ≤ k ≤ n−1, de modo a que na˜o haja arestas entre um ve´rtice
de V1 e um de V2. O nu´mero ma´ximo de arestas de G nessas condic¸o˜es e´(
k
2
)
+
(
n− k
2
)
≤
(
n− 1
2
)
como se pode verificar estudando o modo como o lado esquerdo da desigualdade
varia em func¸a˜o de k.
Se preferirmos um racioc´ınio mais combinato´rio, podemos notar o seguinte:
interpretamos o lado direito da desigualdade como contando o nu´mero de 2-
subconjuntos de [n] que na˜o conteˆm 1, enquanto que o lado esquerdo conta
os 2-subconjuntos de [n] da forma {a, b} com a < b ≤ k ou k < a < b; esta
famı´lia de 2-subconjuntos de [n] tem a mais, em comparac¸a˜o com a anterior, os
k − 1 subconjuntos {1, a} com 1 < a ≤ k, mas tem a menos os (k − 1)(n − k)
subconjuntos {a, b} em que 1 < a ≤ k < b, e portanto temos a desigualdade.
b) Como vimos na al´ınea anterior, o exemplo e´ a unia˜o de Kn−1 com um ve´rtice
isolado.
c) Mais uma vez, o conjunto dos ve´rtices de G desconexo esta´ repartido em
dois conjuntos V1 e V2, disjuntos e na˜o vazios, um com k ve´rtices e o outro com
n− k, onde 1 ≤ k ≤ n− 1, de modo a que na˜o haja arestas entre um ve´rtice de
V1 e um de V2. O grau mı´nimo δ(G) satisfaz com certeza a desigualdade
δ(G) ≤ min{k − 1, n− k − 1}
ja´ que o lado direito nos da´ o grau mı´nimo no caso em G e´ a unia˜o disjunta de
um Kk com um Kn−k. E este atinge o maior valor poss´ıvel quando k = bn/2c
e portanto δ(G) = bn/2c − 1.
d) Se n for par podemos ter G como a unia˜o disjunta de dois Kn/2 e nesse caso
δ(G) = n−22 .
6 - Seja G um grafo com 10 ve´rtices e 28 arestas. Justificar que G conte´m
um ciclo de comprimento 4.
Sugesta˜o: comec¸ar por mostrar que ha´ dois ve´rtices u e v tais que
d(u) + d(v) ≥ 12.
Resoluc¸a˜o: De facto G tem que ter pelo menos dois ve´rtices de grau maior
ou igual a 6: ordenemos os ve´rtices por uma ordem na˜o crescente de graus e
suponhamos que v2, v2, · · · , v10 teˆm todos grau menor que 6; temos por outro
lado d(v1) ≤ 9. Mas enta˜o
10∑
i=1
d(vi) ≤ 9 + 5× 9 = 54,
contradizendo o facto de que
10∑
i=1
d(vi) = |A| = 56.
Sejam enta˜o u e v dois ve´rtices grau maior ou igual a 6. Mesmo que sejam
adjacentes entre si, cada um deles tem que ter pelo menos mais cinco ve´rtices
adjacentes. Mas como so´ ha´ mais 8 ve´rtices, isso implica que u e v sa˜o ambos
adjacentes a (pelo menos) outros dois ve´rtices z e w. A sequeˆncia u, z, v, w
define um ciclo de comprimento 4.
7 - Seja G um grafo simples regular de grau 4. Mostrar que podemos colorir
as arestas de G com duas cores de modo a que em cada ve´rtice incidem duas
arestas de cada cor.
Sugesta˜o: cada componenteconexa de G e´ um grafo Euleriano com um nu´mero
par de arestas.
Resoluc¸a˜o: Basta mostrar que podemos colorir as arestas da forma indicada
em cada componente conexa de G. Como cada componente de G mante´m a
propriedade de ser um grafo simples regular de grau 4, vamos portanto assumir
a partir daqui que G e´ conexo.
Como todos os ve´rtices teˆm grau par, G e´ um grafo Euleriano e tem portanto
um passeio simples fechado que percorre cada aresta exactamente uma vez.
Consideremos um desses passeios e, escolhendo um ve´rtice inicial, percorremos
o passeio, colorindo as arestas alternadamente de azul e vermelho. Se v e´ um
ve´rtice qualquer, o passeio Euleriano escolhido esta´ dividido em duas partes,
uma que comec¸a com a primeira aresta percorrida quando se “sai” de v pela
primeira vez e termina quando se regressa a v, e a outra que comec¸a na segunda
sa´ıda de v.
E´ agora que se torna importante o facto de o nu´mero de arestas ser par, o que
se verifica facilmente:
2|AG| =
∑
v∈VG
d(v) = 4|VG| =⇒ |AG| = 2|VG|.
As duas partes do passeio descritas atra´s teˆm ambas um nu´mero par de arestas
ou um nu´mero ı´mpar de arestas. No primeiro caso, se a primeira aresta per-
corrida for, por exemplo, azul, a u´ltima aresta da primeira parte do passeio e´
vermelha, e portanto a primeira da segunda parte e´ de novo azul e a u´ltima
vermelha. No segundo caso, conclui.se, por um argumento semelhante, que as
primeira e u´ltima arestas da primeira parte do passeio teˆm a mesma cor, en-
quanto que as primeira e u´ltima arestas da segunda parte do passeio teˆm ambas
a outra cor.
8 - Dado n > 0, seja Pet(n) o grafo simples em que os ve´rtices sa˜o os
subconjuntos de [2n + 1] com n elementos, e em que dois ve´rtices S1 e S2 sa˜o
adjacentes se S1 ∩ S2 = ∅.
a) Quantos ve´rtices e arestas tem Pet(n)?
b) Se |S1 ∩ S2| = 1, qual o valor de d(S1, S2) em Pet(n)?
Resoluc¸a˜o: Pet(n) tem
(
2n+ 1
n
)
ve´rtices. Se S e´ um ve´rtice, ou seja,
um n-subconjunto de [2n + 1], pela definic¸a˜o, os ve´rtices adjacentes sa˜o os n-
subconjuntos de [2n+ 1] \ S que tem n+ 1 elementos. Logo d(S) =
(
n+ 1
n
)
=
n+ 1.
Conclui-se que Pet(n) tem
1
2
(n+ 1)
(
2n+ 1
n
)
arestas.
Se n = 1, temos S1 = S2. Podemos portanto supoˆr que n > 1 e que
S1 = {1, 2, · · · , n} e S2 = {n, n + 1, · · · , 2n − 1}, uma vez que o caso geral se
obte´m deste por uma bijecc¸a˜o adequada de [2n+ 1]. Pela definic¸a˜o, os ve´rtices
adjacentes a S1 sa˜o disjuntos deste e e´ fa´cil ver que os que esta˜o a` distaˆncia 2
teˆm n−1 elementos em comum com ele; portanto se n = 2 temos d(S1, S2) = 2;
para n > 2 temos o seguinte caminho em Pet(n)
{1, · · · , n} − {n+ 1, · · · , 2n} − {1, · · · , n− 1, 2n+ 1} − {n, n+ 1, · · · , 2n− 1}
que permite concluir que nesse caso d(S1, S2) = 3.
9 - Um ve´rtice v de um grafo chama-se um corte se G \ v tem mais compo-
nentes conexas que G. Um grafo (com mais do que um ve´rtice) e´ um bloco se
e´ conexo e na˜o tem cortes.
Mostrar que as seguintes propriedades sobre um grafo G com pelo menos treˆs
ve´rtices sa˜o equivalentes:
1- G e´ um bloco;
2- quaisquer dois ve´rtices de G esta˜o em algum ciclo de G;
3- todos os ve´rtice v e aresta a fazem parte de um ciclo de G;
4- quaisquer duas arestas de G esta˜o em algum ciclo de G.
Nota: a condic¸a˜o de G ter pelo menos treˆs ve´rtices e´ necessa´ria porque o
grafo completo em dois ve´rtices e´ um bloco mas na˜o satisfaz nem 2 nem 3. Por
outro lado, a condic¸a˜o de na˜o existirem ve´rtices isolados e´ necessa˜ria porque um
grafo sem arestas satisfaz 3 e 4 trivialmente mas na˜o e´ um bloco.
Resoluc¸a˜o: Provam-se as implicac¸o˜es 1⇒ 2⇒ 3⇒ 4⇒ 1.
1⇒ 2: suponhamos que G e´ um bloco. Dados ve´rtices u e v temos que mostrar
que existe um ciclo que os conte´m.
Para acompanhar o racioc´ınio e´ u´til fazer um diagrama esquema´tico da situac¸a˜o.
Em primeiro lugar, notamos que δ(G) > 1, ja´ que se v fosse um ve´rtice de grau
1, o ve´rtice adjacente a ele seria de corte. Suponhamos enta˜o que u, v ∈ VG
sa˜o adjacentes. Pela observac¸a˜o anterior, v e´ tambe´m adjacente a um terceiro
ve´rtice w; como v na˜o e´ de corte, G \ v e´ conexo e portanto existe um caminho
C em G \ v ligando u a w; mas enta˜o
u↔ v ↔ w C←→ u
e´ um ciclo contendo u e v.
Mostra´mos portanto que dois ve´rtices adjacentes em G pertencem sempre a um
ciclo; de facto, o racioc´ınio mostra que se d(u, v) = 2 a propriedade ainda se
verifica. Para tentarmos generalizar, consideremos o caso seguinte, d(u, v) = 3;
temos enta˜o
u↔ x↔ y ↔ v;
o racioc´ınio anterior mostra que existem caminhos C1 e C2 que criam os ciclos
u↔ x↔ y C1←→ u
e
x↔ y ↔ v C2←→ x;
se C1 conte´m v ou C2 conte´m u, ja´ tmeos um ciclo contendo u e v; caso contra´rio,
podemos construir esse ciclo do seguinte modo
u↔ x C2←→ v ↔ y C1←→ u.
Esta construc¸a˜o poderia ser generalizada de modo a obter uma “receita“ para
definir, recursivamente, ciclos contendo ve´rtices a distaˆncias maiores. De forma
menos construtiva mas mais simples, podemos usar esta ideia para demonstrar
a propriedade por induc¸a˜o na distaˆncia entre os dois ve´rtices. Ja´ verifica´mos
que se d(u, v) ≤ 3 existe um cilco em G contendo os dois ve´rtices.
Suponhamos, como hipo´tese de induc¸a˜o, que se d(u, x) = n enta˜o existe um
ciclo contendo u e x; se d(u, v) = n + 1, enta˜o existe um ve´rtice x adjacente a
v, tal que d(u, x) = n; por hipo´tese de induc¸a˜o u e x esta˜o contidos num ciclo
C; caso v ∈ C na˜o ha´ nada a provar; caso contra´rio, como G e´ um bloco, G \ x
e´ conexo; seja y o ve´rtice de C mais pro´ximo de v em G \ x e C ′ um caminho
ligando v a y em G \ x; note-se que C ′ na˜o conte´m outros ve´rtices de C ale´m
de y; chamando C1 ao caminho ligando u a x em C que na˜o conte´m y e C2 ao
caminho que liga u a y em C e que na˜o conte´m x (e´ neste ponto que um desenho
se torna u´til).
Constru´ımos enta˜o o ciclo
u
C1←→ x↔ v C
′
←→ y C2←→ u.
2 ⇒ 3: seja v um ve´rtice e a uma aresta de extremos x e y; se v = x (
ou v = y), como 2 implica que x e y esta˜o num ciclo, temos que v e a esta˜o
num ciclo, portanto podemos supoˆr que a aresta a na˜o incide em v. A condic¸a˜o
2 implica que v e x esta˜o num ciclo, ou seja, existem dois caminhos C1 e C2
unindo v a x, disjuntos a` excepc¸a˜o dos extremos. Por outro lado, como tambe´m
v e y esta˜o em algum ciclo, existe um caminho Q com in´ıcio em v e fim em y
que na˜o passa por x (caso contra´rio, na˜o poderiam existir caminhos disjuntos
unindo v a y). Seja z o u´ltimo ve´rtice de Q que pertence tambe´m a C1 ∪ C2
e que supoˆmos estar por exemplo em C1. O caminho que consiste na unia˜o de
C2 com a aresta a, com a parte do caminho Q entre y e z e com a parte de C1
entre v e z e´ um ciclo nas condic¸o˜es pretendidas.
A implicac¸a˜o 3 ⇒ 4 pode provar-se de modo semelhante. Quanto a 4 ⇒ 1,
notamos em primeiro lugar que como na˜o ha´ ve´rtices isolados a condic¸a˜o 4
implica que G e´ conexo. Seja u um ve´rtice e mostremos que, na condic¸a˜o de
G satisfazer 4, G \ u e´ conexo: dados dois ve´rtices x e y e duas arestas a e
b incidentes em x e y respectivamente, sabemos que existe um ciclo contendo
estas arestas; pelo menos um dos caminhos unindo x a y nesse ciclo na˜o conte´m
u; portanto existe um caminho entre x e y em G \ u.
10 - O Museu Mundial dos Grafos esta´ instalado num edif´ıcio cu´bico, di-
vidido em 27 salas cu´bicas (nove por andar). Cada sala tem comunicac¸a˜o com
todas as salas adjacentes (ou seja todas aquelas com as quais tem uma face
em comum). A entrada esta´ numa das salas de esquina do primeiro piso. Sera´
poss´ıvel fazer uma visita ao Museu, passando uma u´nica vez em cada sala e
terminando na sala que se situa no centro do edif´ıcio?
Resoluc¸a˜o: Consideramos o grafo cujos ve´rtices sa˜o as salas e cujas arestas
sa˜o as passagens entre salas. As oito salas localizadas nos cantos do edif´ıcio teˆm
grau 3, enquantoas outras teˆm graus 4, 5 e a sala central tem grau 6. O que se
pergunta e´ se existe um caminho hamiltoniano com in´ıcio num dos ve´rtices de
grau 3 e fim no ve´rtice de grau 6.
Uma maneira pra´tica de abordar o problema e´ representar o gra´fico de maneira
ana´loga ao grafo do problema 14 da Ficha 10: cada sala (ve´rtice e´ representada
por uma tripla {a1, a2, a3} com ai ∈ {0, 1, 2}: colocamos um dos ve´rtices do
cubo na origem de um sistema de eixos cartesiano, alinhando as arestas ao
longo dos semieixos positivos, e atribu´ımos a cada sala as coordenadas do seu
ve´rtice mais pro´ximo da origem. Nesta descric¸a˜o, os ve´rtices e arestas referidos
sa˜o os do cubo e na˜o os do grafo, evidentemente.
A observac¸a˜o fundamental e´ que passar de um ve´rtice do grafo a um ve´rtice
adjacente, altera uma das coordenadas numa unidade sem alterar os valores
das outras. Portanto, ao percorrer um caminho no grafo, a paridade da soma
das coordenadas vai alternando: partindo do ve´rtice (sala) origem, comec¸amos
com par, passamos a ı´mpar, depois par, etc. Ora, um caminho hamiltoniano
na˜o fechado neste grafo tem exactamente 26 arestas e portanto, partindo de
um ve´rtice com soma de coordenadas par, temos que terminar num ve´rtice com
soma de coordenadas igualmente par. Mas a sala central, tem coordenadas
{1, 1, 1}.
11 - Dado um grafo conexo de diaˆmetro D e grau ma´ximo ∆,
a) Fixando um ve´rtice v0, provar que o nu´mero de ve´rtices a` distaˆncia k de
v0 e´ menor ou igual a ∆(∆− 1)k−1;
b) Concluir que o nu´mero total de ve´rtices de G e´ menor ou igual a
1 + ∆
(∆− 1)D − 1
∆− 2
Resoluc¸a˜o: A al´ınea a) e´ imediata: existem no ma´ximo ∆ ve´rtices a` distaˆcia
1 de v0; cada um deles tem no ma´ximo ∆ − 1 outros ve´rtices adjacentes que
esta˜o a` distaˆncia 2 de v0 e assim por diante.
b) decorre de notar que contando os ve´rtices de acordo com a distaˆncia a v0, o
seu nu´mero total e´ menor ou igual a
1 + ∆ + ∆(∆− 1) + · · ·+ ∆(∆− 1)D−1 = 1 + ∆
D−1∑
k=0
(∆− 1)k =
= 1 + ∆
1− (∆− 1)D
1− (∆− 1) = 1 + ∆
(∆− 1)D − 1
∆− 2
12 - Mostrar que num grafo conexo, dois caminhos de comprimento ma´ximo
teˆm sempre pelo menos um ve´rtice em comum.
Resoluc¸a˜o: Suponhamos que temos dois caminhos disjuntos C1 e C2 de
comprimento ma´ximo m− 1, o primeiro com a sequeˆncia de ve´rtices
x1, · · · , xm
e o segundo com
y1, · · · , ym;
como o grafo e´ conexo, existe um caminho de x1 ate´ ym; podemos considerar
que esse caminho percorre C1 de x1 ate´ um certo xi com 1 ≤ i ≤ m, depois um
caminho C de comprimento l ≥ 1 entre xi e yj , com 1 ≤ j ≤ m e depois C2 de
yj ate´ ym. Este caminho tem comprimento i− 1 + l +m− j.
Do mesmo modo, o caminho entre y1 e xm que percorre C2 de y1 ate´ yj , depois
C de yj ate´ xi, e finalmente C1 de xi ate´ xm, tem comprimento j−1+ l+m− i.
Como a soma dos comprimentos destes dois caminhos e´
2m+ 2l − 2 ≥ 2m
um deles teria que ter comprimento maior ou igual a m, contradizendo a nossa
hipo´tese. Portanto os caminhos na˜o sa˜o disjuntos.
13 - - Determinar quantos automorfismos teˆm os seguintes grafos:
a) O grafo completo Kn;
b) Um ciclo Cn com n ve´rtices;
c) O grafo que se obte´m de Kn eliminando 3 arestas (considerar os cinco
casos poss´ıveis) .
Sugesta˜o para a al´ınea c): Notar que f : V → V e´ um automorfismo de um
grafo com ve´rtices V se e so´ se for tambe´m um automorfismo do seu comple-
mentar.
Resoluc¸a˜o: Qualquer permutac¸a˜o dos ve´rtices e´ um automorfismo de Kn,
portanto a resposta para a al´ınea a) ’e n!.
Na al´ınea b) a resposta e´ 2n que e´ o nu´mero de simetrias de um pol´ıgono regular
com n lados, correspondendo a n rotac¸o˜es e n reflexo˜es (ver a descric¸a˜o mais
pormenorizada feita aquando do estudo de contagem com simetria).
Na al´ınea c), e seguindo a sugesta˜o, estudamos os grafos complementares. Con-
sideremos primeiro o caso em que as treˆs arestas eliminadas incidem num ve´rtice
comum (o que so´ pode acontecer se n > 3) : o grafo complementar e´ a unia˜o de
uma a´rvore com um ve´rtice de grau 3 e treˆs ve´rtices de grau 1, com n−4 ve´rtices
isolados. Um automorfismo deste grafo e´ determinado por uma permutac¸a˜o
das treˆs folhas da a´rvore e por uma permutacca˜o qualquer dos restantes n − 4
ve´rtices. Temos portanto 3!× (n− 4)! automorfismos poss´ıveis.
Um segundo caso e´ aquele em que as treˆs arestas eliminadas na˜o teˆm ve´rtices in-
cidentes em comum, mais precisamente, quando formam um emparelhamento.
Nesse caso, o grafo complementar consiste na unia˜o de treˆs grafos com dois
ve´rtices e uma aresta cada um, com n − 6 ve´rtices isolados. A acc¸a˜o de um
automorfismo na unia˜o dos treˆs grafos indicados e´ determinada pelas imagens
de um dos ve´rtices de cada um dos grafos: suponhamos que os treˆs pares de
ve´rtices adjacentes sa˜o
{v1, v2}, {v3, v4}, {v5, v6};
a imagem de v1 por um automorfismo φ pode ser qualquer dos vi; mas essa es-
colha determina φ(v2); φ(v3) pode ser qualquer dos vi, excepto φ(v1) ou φ(v2),
e φ(v4) fica determinado; finalmente φ(v5) pode ser um dos dois ve´rtices restan-
tes. Conclui-se que temos 6×4×2 acc¸o˜es poss´ıveis e portanto 48 automorfismos
distintos.
Podemos descrever a acc¸a˜o de um automorfismo na unia˜o destes treˆs grafos
como a composic¸a˜o de uma permutacca˜o dos treˆs grafos com uma permutac¸a˜o
dos dois ve´rtices de cada grafo, o que nos da´, como vimos, 3!× 23 casos.
Temos ainda que multiplicar este valor por (n− 6)! que e´ o nu´mero de permu-
tacco˜es dos restantes ve´rtices. Logo no segundo caso temos 3!× 8times(n− 6)!
automorfismos.
Os restantes casos tratam-se de modo semelhante.
14 - Dada uma a´rvore T e um ve´rtice v0, definimos a excentricidade de v0
como a distaˆncia ma´xima de v0 aos outros ve´rtices de T, e dizemos que v0 e´ um
centro de T se for um ve´rtice de excentricidade mı´nima.
Mostrar que uma a´rvore tem ou 1 ou 2 centros.
Resoluc¸a˜o: Embora seja poss´ıvel fazer a demonstrac¸a˜o por induc¸a˜o, e´ mais
fa´cil raciocinar directamente. Vamos designar d(u, v) a distaˆncia entre dois
ve´rtices u e v.
Mostramos que numa a´rvore dois centros u e v teˆm que ser adjacentes; suponha-
mos que na˜o e sejam enta˜o u e v dois centros e w um ve´rtice no u´nico caminho
que une u a v; dado um ve´rtice qualquer z, verifica-se uma das seguintes si-
tuac¸o˜es: ou o caminho entre w e z passa por u, ou passa por v, ou enta˜o os
caminhos de u e de v para z passam por w.
Mas enta˜o
d(w, z) < max{d(u, z), d(v, z)}
e portanto a excentricidade de w seria menor que a dos centros, o que e´ im-
poss´ıvel.
A conclusa˜o e´ agora imediata: se existirem treˆs centros, eles teˆm que ser adja-
centes entre si, contradizendo o facto de estarmos numa a´rvore.
15 - Provar que uma a´rvore com um nu´mero par de arestas tem pelo menos
um ve´rtice de grau par.
Resoluc¸a˜o:Temos |V | = n e |A| = n − 1 = 2k, logo |V | = 2k + 1; se
todos os ve´rtices tivessem grau ı´mpar, a soma dos graus daria tambe´m ı´mpar,
contradizendo a fo´rmula ∑
d(v) = 2|A|
.
16 - Dada uma a´rvore de ordem n > 1, mostrar que o nu´mero de folhas
(ve´rtices de grau 1) e´ igual a
2 +
∑
d(v)≥2
(d(v)− 2)
em que a soma se faz sobre todos os ve´rtices com grau maior ou igual a 2.
Resoluc¸a˜o: Usamos induc¸a˜o em n. A afirmac¸a˜o e´ verdadeira para n = 2,
porque ambos os ve´rtices sa˜o folhas (e na˜o ha´ ve´rtices de grau maior que 1).
Supondo que e´ verdadeira para um certo n, tomamos uma a´rvore de ordem n+1
e consideramos a a´rvore T ′ que se obte´m eliminando um dos ve´rtices de grau 1
e a aresta incidente; T ′ tem, por hipo´tese de induc¸a˜o,
2 +
∑
d(v)≥2
(d(v)− 2)
ve´rtices de grau 1, onde a soma se faz sobre todos osve´rtices de grau maior que
1 em T ′.
Se o ve´rtice u adjacente ao que elimina´mos tinha grau 1 em T ′, passou a ter
grau 2 em T e o nu´mero de ve´rtices de grau 1 na˜o mudou, mas u contribui 0
para o valor da expressa˜o; se u tinha grau maior que1, o nu´mero de ve´rtices
de grau 1 aumentou uma unidade, e o grau de u tambe´m, pelo que a expressa˜o
continua va´lida.
17 - Seja a uma aresta de Kn. Mostrar que Kn−a tem (n−2)nn−3 a´rvores
geradoras.
Resoluc¸a˜o: Usamos a fo´rmula
t(G) = t(G \ a) + t(G/a),
onde t(G) designa o nu´mero de a´rvores geradoras de G. No nosso caso, t(Kn) =
nn−2 pela fo´rmula de Cayley. Como queremos saber o valor da primeira parcela
do lado direito da igualdade, basta calcular a segunda parcela. Os dois ve´rtices
incidentes na aresta a, em Kn, sa˜o substitu´ıdos, em Kn/a, por um u´nico ve´rtice
de grau 2(n− 2): para cada um dos restantes n− 2 ve´rtices do grafo, existem 2
arestas paralelas correspondendo a`s arestas que ligavam cada um desses ve´rtices
aos dois ve´rtices de Kn. Ou seja, Kn/a pode ser visto como Kn−1, em que cada
aresta incidente num ve´rtice, que podemos designar como v1, e´ substitu´ıda por
um par de arestas paralelas.
Podemos calcular enta˜o t(Kn/a) adaptando o co´digo de Pru¨fer: o ı´ndice 1 consta
do co´digo de uma das a´rvores geradoras de Kn−1 k−1 vezes, em que k e´ o grau
de v1 nessa a´rvore. Se contarmos os co´digos de Pru¨fer das a´rvores geradoras de
Kn−1 pelo grau de v1, temos um somato´rio
n−3∑
j=0
(
n− 3
j
)
(n− 2)n−3−j :
escolhemos j posic¸o˜es para os 1 e preenchemos as restantes com os outros valores.
Pelo Teorema do Bino´mio, o resultado e´, como ja´ sabemos, (n− 1)n−3.
No caso de a´rvores geradoras de Kn/a, cada parcela desse somato´rio tem que
ser multiplicada por 2j+1: se v1 tem grau j + 1 na a´rvore, para cada um dos
ve´rtices adjacentes temos que escolher qual das duas arestas paralelas usamos.
Mass enta˜o
t(Kn/a) =
n−3∑
j=0
(
n− 3
j
)
2j+1(n−2)n−3−j = 2
n−3∑
j=0
(
n− 3
j
)
2j(n−2)n−3−j = 2(2+n−2)n−3 = 2nn−3,
aplicando mais uma vez o Teorema do Bino´mio.
Conclu´ımos que
t(Kn − a) = t(Kn)− t(Kn/a) = nn−2 − 2nn−3 = nn−3(n− 2).
18 - Dado um grafo conexo G e um ve´rtice v0, mostrar que existe uma a´rvore
geradora T , tal que, para todo o ve´rtice v, a distaˆncia entre v0 e v em T e´ igual
a` distaˆncia entre v0 e v em G.
Resoluc¸a˜o: Constru´ımos uma a´rvore geradora T com o algoritmo gananci-
oso, usando o ve´rtice v0 como raiz e usando busca em largura.
Podemos raciocinar por induc¸a˜o: todas as arestas incidentes em v0 sa˜o inclu´ıdas
na a´rvore e portanto os ve´rtices que esta˜o a` distaˆncia 1 de v0 em G, ficam a`
mesma distaˆncia em T (e sa˜o os u´nicos nessa situac¸a˜o); em seguida o algoritmo
procura os ve´rtices adjacentes a estes que ainda na˜o estejam em T e assim por
diante; suponhamos que os ve´rtices a` distaˆncia k de v0 em G sa˜o exactamente
os que ficam a` mesma distaˆncia em T e seja v um ve´rtice a` distaˆncia k + 1 de
v0; v na˜o pode ser inclu´ıdo em T antes do algoritmo fazer a busca nos ve´rtices
adjacentes aos que esta˜o a` distaˆncia k de v0; mas v e´ adjacente a algum destes
e vai portanto ser inclu´ıdo em T nesse passo do algoritmo.
19 - Mostrar que uma sequeˆncia
d1 ≥ d2 ≥ · · · ≥ dn ≥ 1
e´ a sequeˆncia ordenada de graus de uma a´rvore com n > 1 ve´rtices v1, · · · , vn,
se e so´ se
n∑
i=1
di = 2(n− 1).
Resoluc¸a˜o: A condic¸a˜o e´ necessa´ria porque uma a´rvore com n ve´rtices tem
n − 1 arestas e portanto a soma dos graus dos ve´rtices tem que ser igual a
2(n − 1). Note-se ale´m disso que a condic¸a˜o implica que dn = 1, uma vez que
se di ≥ 2 para todo o i, enta˜o
∑n
i=1 di ≥ 2n. Por outro lado,
2n− 2 =
n∑
i=1
di ≤ nd1
e portanto d1 > 1.
Provamos por induc¸a˜o em n que a condic¸a˜o e´ tambe´m suficiente. Para n = 2 a
u´nica sequeˆncia que satisfaz a condic¸a˜o e´ {1, 1} que e´ a sequeˆncia de graus da
u´nica a´rvore com ve´rtices v1, v2.
Suponhamos que a condic¸a˜o e´ suficiente para algum n e seja
d1 ≥ d2 ≥ · · · ≥ dn ≥ dn+1 ≥ 1
uma sequeˆncia satisfazendo
n+1∑
i=1
di = 2(n+ 1− 1) = 2n.
Seja i um ı´ndice qualquer com di > 1; a sequeˆncia
d1, · · · , di − 1, · · · , dn
reordenada, se necessa´rio, satisfaz as condic¸o˜es do enunciado e portanto existe
uma a´rvore em ve´rtices v1, · · · , vn que tem esta sequeˆncia de graus; juntando
uma folha vn+1 adjacente a vi obtemos uma a´rvore nas condic¸o˜es desejadas.
20 - Mostrar que o nu´mero de a´rvores com ve´rtices v1, · · · , vn (n > 1) para
as quais d(vi) = di e´ dado por
(n− 2)!
(d1 − 1)! · · · (dn − 1)!
Sugesta˜o: usar induc¸a˜o em n; notar que podemos assumir que dn = 1.
Usando o teorema multinomial, deduzir a fo´rmula de Cayley.
Resoluc¸a˜o: A fo´rmula e´ va´lida para n = 2. Suponhamos que ela vale para
um certo n e seja
d1 ≥ d2 ≥ · · · ≥ dn ≥ dn+1
uma sequeˆncia de graus satisfazendo a condic¸a˜o do exerc´ıcio anterior. Como se
viu, isso implica que dn+1 = 1, ou seja, que o ve´rtice vn+1 e´ uma folha. Dada
uma a´rvore T com essa sequeˆncia de graus, se eliminarmos esta folha, obtemos
uma nova a´rvore T ′, com n ve´rtices, em que um dos ve´rtices que em T tinha
grau di > 1 tem agora grau di − 1, mantendo-se os outros graus inalterados.
Suponhamos que dk > 1 = dk+1, isto e´, k e´ o maior ı´ndice para o qual o grau e´
maior que 1. Para cada 1 ≤ i ≤ k, existem, pela hipo´tese de induc¸a˜o,
(n− 2)!
(d1 − 1)! · · · (di−1 − 1)!(di − 2)!(di+1 − 1)! · · · (dn − 1)!
a´rvores com aquela sequeˆncia de graus. E reciprocamente, como se viu no
exerc´ıcio anterior, se tivermos uma a´rvore com ve´rtices
v1, · · · , vn
tal que
d(vj) =
{
dj se j 6= i
di − 1 se j = i ,
acrescentando uma folha vn+1 adjacente ao ve´rtice vi, obtemos uma a´rvore nas
condic¸o˜es iniciais.
Portanto, somando sobre todos os valores poss´ıveis de i, existem
k∑
i=1
(n− 2)!
(d1 − 1)! · · · (di−1 − 1)!(di − 2)!(di+1 − 1)! · · · (dn − 1)!
a´rvores com a sequeˆncia de graus
d1 ≥ d2 ≥ · · · ≥ dn ≥ dn+1.
Mas, reduzindo ao mesmo denominador,
k∑
i=1
(n− 2)!
(d1 − 1)! · · · (di−1 − 1)!(di − 2)!(di+1 − 1)! · · · (dn − 1)! =
= (n− 2)!
k∑
i=1
(di − 1)
(d1 − 1)! · · · (dn − 1)! =
= (n− 2)!
∑k
i=1(di − 1)
(d1 − 1)! · · · (dn − 1)!(dn+1 − 1)! =
ja´ que estamos apenas a multiplicar o denominador por 0! = 1,
= (n− 2)!
∑n+1
i=1 (di − 1)
(d1 − 1)! · · · (dn − 1)!(dn+1 − 1)!
que corresponde a somar no numerador parcelas nulas; e como
∑n+1
i=1 di = 2(n+
1− 1), temos
(n− 2)!
∑n+1
i=1 (di − 1)
(d1 − 1)! · · · (dn − 1)!(dn+1 − 1)! =
= (n− 2)! 2n− (n+ 1)
(d1 − 1)! · · · (dn − 1)!(dn+1 − 1)! =
(n− 1)!
(d1 − 1)! · · · (dn+1 − 1)!
como quer´ıamos demonstrar.
O Teorema multinomial diz-nos que
(x1 + x2 + · · ·+ xn)n−2 =
=
∑( n− 2
k1, k2, · · · , kn
)
xk11 x
k2
2 · · ·xknn
em que a soma se faz sobre todos as sequeˆncias k1, k2, · · · , kn satisfazendo as
condic¸o˜es
0 ≤ ki ∀i; k1 + k2 + · · ·+ kn = n− 2.
Pondo di = ki + 1, estas condic¸o˜es sa˜o equivalentes a ter di > 0 e
∑n
i=0 di =
2(n − 1), ou seja, cada escolha poss´ıvel dos ki corresponde a uma sequeˆncia
poss´ıvel de graus di = d(vi). Fazendo xi = 1, para todos os i, obtemos
nn−2 =
∑ (n− 2)!
(d1 − 1)! · · · (dn − 1)!
e como do lado direito somamos o nu´mero de a´rvores de cada sequeˆncia de
graus, temos a fo´rmula de Cayley: o conjunto de todas as a´rvores com ve´rtices
v1, · · · , vn tem nn−2 elementos.
21 - Seja k > 0 e T uma a´rvore qualquer com k + 1 ve´rtices, dos quais
escolhemos um para raiz. Mostrar que se G e´ um grafo simples com grau
mı´nimo (maior ou igual a) k, para qualquer ve´rtice v de G, existe um subgrafo
de G isomorfo a T em que a raiz e´ v.
Sugesta˜o: induc¸a˜o.
Resoluc¸a˜o: Se k = 1, a propriedade verifica-se: se T e´ uma a´rvore com
dois ve´rtices, dado qualquer grafo G com grau mı´nimo maior ou igual a 1 e um
ve´rtice v, escolhemos um ve´rtice u adjacente a v (tem que exsitir pelo menos
um); u, v e a aresta incidente a ambos e´ um subgrafo de G isomorfo a T .
Suponhamos que a propriedade se verifica para um certo k; seja agora Tuma
a´rvore com k+2 ve´rtices com uma raiz r, G um grafo com grau mı´nimo δ(G) ≥
k + 1, e v um ve´rtice de G. Seja s uma folha de T (que na˜o seja a raiz r) e t o
ve´rtice adjacente. Por hipo´tese de induc¸a˜o, existe um subgrafo de G isomorfo a`
a´rvore T − s com raiz r; mais precisamente, existe uma aplicac¸a˜o injectiva
h : V (T − s)→ V (G)
tal que x e y sa˜o adjacentes em T − s se e so´ se h(x) e h(y) sa˜o adjacentes em
G e ale´m disso h(r) = v.
Seja u = h(t); como T − s tem k + 1 ve´rtices, um dos quais t, mas o grau de u
em G e´ pelo menos k + 1, existe pelo menos um ve´rtice w adjacente a u em G
que na˜o pertence a` imagem de h; portanto podemos prolongar a definic¸a˜o de h
a s, fazendo h(s) = w.
22 - Dados dois conjuntos disjuntos
V = {v1, · · · , vm}, U = {u1, · · · , un}
calcular o nu´mero de a´rvores com ve´rtices V ∪ U , em que cada aresta incide
num ve´rtice de V e noutro de U , contando as ramificac¸o˜es em V ∪ U com raiz
em V .
Resoluc¸a˜o: Recorde-se que uma ramificac¸a˜o e´ uma a´rvore com as arestas
orientadas de modo a que cada ve´rtice tenha no ma´ximo uma aresta de entrada;
ou de forma equivalente, uma a´rvore com um ve´rtice raiz e em que cada aresta e´
orientada do ve´rtice mais pro´ximo da raiz para o outro; a raiz e´ o u´nico ve´rtice
que na˜o tem arestas de entrada.
Constru´ımos uma ramificac¸a˜o, com a condic¸a˜o de que a raiz fica em V mas
sem fixar a` partida em que ve´rtice. Tendo em conta a observac¸a˜o feita no
para´grafo anterior, essa ramificac¸a˜o tera´ n arestas com in´ıcio em V , cada uma
delas terminando num dos ve´rtices de U , e m− 1 arestas com in´ıcio em U , cada
uma delas terminando num dos ve´rtices de V menos na raiz.
Se criarmos primeiro as arestas de V para U , uma de cada vez, vemos que isso
pode ser feito de mn × n! maneiras: cada aresta pode ter in´ıcio num qualquer
dos vi; temos n escolhas para ve´rtice final da primeira aresta, n − 1 para a
segunda, etc.
Neste ponto temos uma floresta com m componentes, cada uma delas com um
dos vi ∈ V como raiz. Em seguida criamos as m− 1 arestas de U para V : cada
uma delas pode ter in´ıcio num qualquer u ∈ U mas o ve´rtice final na˜o pode ser
a raiz da componente a que u pertence; temos enta˜o m − 1 escolhas de ve´rtice
final para a primeira destas arestas; no passo seguinte o nu´mero de ramificac¸o˜es
ja´ criadas diminuiu para m − 1 e portanto, escolhido o ve´rtice inicial u, so´ ha´
m− 2 escolhas de ve´rtice final, e assim por diante. Conclui-se que estas arestas
podem ser escolhidas ordenadamente de nm−1 × (m− 1)! maneiras.
Note-se que no final ha´ exactamente um ve´rtice em V que na˜o foi escolhido para
ve´rtice final de uma das arestas e esse e´ a raiz da ramificac¸a˜o.
Mas cada ramificac¸a˜o pode ser obtida, por este processo de (m − 1)! × n!
maneiras, uma por cada ordenac¸a˜o das arestas de V para U e das arestas de U
para V . Portanto ha´ nm−1 ×mn ramificac¸o˜es com raiz em V .
Logo ha´ nm−1 ×mn−1 a´rvores nas condic¸o˜es pedidas, uma vez que cada uma
delas da´ origem a m ramificac¸o˜es com raiz em V .
Note-se que o problema equivale a contar o nu´mero de a´rvores geradoras do
grafo bipartido completo Km,n.
23 - Mostrar que se G e´ um grafo conexo planar com n ve´rtices e m arestas
e em que o menor ciclo tem comprimento k, enta˜o
m ≤ kn− 2
k − 2 .
Resoluc¸a˜o: Numa representac¸a˜o planar de G, o conjunto de arestas que
limitam uma face conte´m um ciclo; por outro lado, quando contamos os lados
de cada face e somamos pra todas as faces o resultado iguala o dobro do nu´mero
de arestas. Portanto
2m ≥ fk;
mas a fo´rmula de Euler diz-nos que f = 2+m−n; substituindo na desigualdade
anterior obte´m-se o resultado do enunciado.
24 - Mostrar que o grafo complementar de um grafo simples planar com
n ≥ 11 ve´rtices, na˜o e´ planar.
Resoluc¸a˜o: se G e´ planar simples sabemos que o nu´mero m de arestas
satisfaz
m ≤ 3n− 6;
mas G tem
(
n
2
)−m arestas. Se mostrarmos que(
n
2
)
−m > 3n− 6
ou seja, que (
n
2
)
−m− 3n+ 6 > 0
fica provado que G na˜o e´ planar. Usando a desigualdade anterior(
n
2
)
−m− 3n+ 6 ≥
(
n
2
)
− 6n+ 12 = n(n− 1)− 12n+ 24
2
=
n2 − 13n+ 24
2
;
como as raizes do polino´mio no numerador sa˜o 13±
√
73
2 , e 11 >
13+
√
73
2 obtemos
a desigualdade desejada.
25 - Mostrar que e´ poss´ıvel ordenar os ve´rtices de um grafo G de modo a
que o algoritmo ganancioso de colorac¸a˜o use apenas χ(G) cores.
Resoluc¸a˜o: Suponhamos que temos os grafo colorido com um nu´mero
mı´nimo de cores c1, c2, · · · ck, onde k = χ(G); isso corresponde a termos uma
decomposic¸a˜o
V = V1 ∪ V2 ∪ · · · ∪ Vk
dos ve´rtices em conjuntos esta´veis na˜o vazios e disjuntos dois a dois.
Ordenemos os ve´rtices usando esta ordem: primeiros os que esta˜o em V1 (por
qualquer ordem), depois os de V2, etc. Se aplicarmos o algoritmo ganancioso a
esta ordem dos ve´rtices e das cores, os ve´rtices de V1 va˜o ser todos coloridos com
a cor c1, uma vez que sa˜o na˜o adjacentes entre si. Quando passamos aos ve´rtices
de V2 o algoritmo ou usa a cor c1, se o ve´rtice em questa˜o na˜o for adjacente a
nenhum ve´rtice de V1, ou usa a cor c2, caso contra´rio; em qualquer caso, nunca
e´ usada uma terceira cor; por outro lado, a segunda cor tera´ obrigatoriamente
que ser usada antes de o algoritmo terminar de colorir os ve´rtices de V2, ja´ que
se nenhum ve´rtice de V2 fosse adjacente a nenhum de V1, estes dois conjuntos
esta´veis poderiam ser reunidos num so´, diminuindo o nu´mero de componentes
na decomposic¸a˜o e portanto ter´ıamos χ(G) < k.
Do mesmo modo, vemos que quando o algoritmo percorre os ve´rtices de Vi, ou
usa uma das i − 1 cores ja´ usadas antes, ou a nova cor ci se o ve´rtice a colorir
for adjacente a algum ve´rtice em cada um dos conjuntos Vj , com j < i - o que,
como veremos no exerc´ıcio seguinte, tera´ forosamente que acontecer - mas nunca
usa outra cor. Portanto conclu´ımos que o algoritmo usa exactamente k cores. O
racioc´ınio anterior pode ser formalizado com recurso a induc¸a˜o: provamos que,
com aquela ordem dos ve´rtices, o algoritmo ganancioso ao colorir os ve´rtices de
Vi nunca usa mais do que i cores.
26 - Seja G um grafo com χ(G) = k e
V = V1 ∪ · · · ∪ Vk
uma partic¸a˜o dos ve´rtices em conjuntos esta´veis, um para cada cor. Mostrar
que para cada i ≤ k existe algum v ∈ Vi que tem ve´rtices adjacentes de todas
as outras cores. Em particular, G tem que conter pelo menos k ve´rtices de grau
maior ou igual a k − 1.
Sugesta˜o: analisar a negac¸a˜o da afirmac¸a˜o contida no enunciado.
Resoluc¸a˜o: A afirmac¸a˜o do enunciado escreve-se simbolicamente
∀i ≤ k ∃v ∈ Vi ∀j 6= i ∃u ∈ Vj : v, u sa˜o adjacentes.
A negac¸a˜o desta proposic¸a˜o e´
∃i ≤ k ∀v ∈ Vi ∃j 6= i ∀u ∈ Vj : v, u na˜o sa˜o adjacentes.
Mas se esta u´ltima proposic¸a˜o fosse verdadeira poder´ıamos distribuir os ve´rtices
de Vi pelos outros conjuntos esta´veis sem que eles perdessem esta propriedade,
o que teria como consequeˆncia que χ(G) < k, ao contra´rio do que se diz no
enunciado. Portanto a primeira proposic¸a˜o e´ verdadeira.
A u´ltima afirmac¸a˜o e´ agora evidente: para cada i ≤ k, o ve´rtice v cuja existeˆncia
e´ garantida pela proposic¸a˜o tem pelo menos um ve´rtice adjacente em cada um
dos outros conjuntos esta´veis da decomposic¸a˜o e portanto tem grau maior ou
igual a k − 1.
27 - Ordenamos os ve´rtices de um grafo por ordem decrescente de grau
d(v1) ≥ d(v2) ≥ · · · ≥ d(vn)
e definimos l = max{0 ≤ i ≤ n : i ≤ d(vi) + 1}.
Mostrar que se aplicarmos o algoritmo ganancioso de colorac¸a˜o a essa ordem
dos ve´rtices, nunca usamos mais do que l cores.
Resoluc¸a˜o: Vamos designar di = d(vi). Pela condic¸a˜o dada, temos l ≤ dl+1
mas l+ 1 > dl+1 + 1, e isto equivale a definir l como o u´nico ı´ndice que satisfaz
as desigualdades
dl+1 < l ≤ dl + 1.
Analisemos a aplicac¸a˜o do algoritmo ganancioso com esta ordem de ve´rtices:para i ∈ {1, · · · , l} e´ evidente que na˜o usamos mais do que l cores; se i > l ao
colorir vi temos na pior das hipo´teses, todos os di ve´rtices adjacentes ja´ coloridos
e com di cores diferentes; mas di ≤ dl+1 < l e portanto existe seguramente
alguma cor dispon´ıvel entre as l cores.
28 - Mostrar que dado um grafo de ordem n
n
α(G)
≤ χ(G) ≤ n+ 1− α(G)
onde α(G) designa o nu´mero ma´ximo de ve´rtices num conjunto esta´vel.
Resoluc¸a˜o: Seja χ(G) = k e
V = V1 ∪ · · · ∪ Vk
uma decomposic¸a˜o em conjuntos esta´veis, disjuntos dois a dois. Pela definic¸a˜o
|Vi| ≤ α(G), logo
n =
k∑
i=1
|Vi| ≤ kα(G);
a segunda desigualdade e´ igualmente simples: se escolhermos um conjunto
esta´vel com alpha(G) ve´rtices e os colorirmos todos com uma cor, precisamos,
na pior das hipo´teses, de uma outra cor para cada um dos restantes n − α(G)
ve´rtices.
29 -
a) Dados grafos G e H com o mesmo conjunto de ve´rtices V , definimos G∨H
como sendo o grafo com ve´rtices V e em que u, v ∈ V sa˜o adjacentes se e
so´ se o sa˜o em G ou em H (ou em ambos). Mostrar que
χ(G ∨H) ≤ χ(G)χ(H).
Concluir que χ(G)χ(G) ≥ n.
b) Mostrar que 2
√
n ≤ χ(G) + χ(G) ≤ n+ 1.
Sugesta˜o para a segunda desigualdade da al´ınea b): usar o exerc´ıcio 27
anterior.
Resoluc¸a˜o: a) A ideia e´ que se G foi colorido com cores c1, · · · , ck e H com
cores c′1, · · · , c′l, podemos colorir G ∨ H com pares de cores: se o ve´rtice v foi
colorido em G com a cor ci e em H com a cor c
′
j , atribuimos-lhe em G ∨H a
cor (ci, c
′
j), seguindo-se o resultado. Vendo o problema em termos de conjuntos
esta´veis, existe uma decomposic¸a˜o
V = V1 ∪ · · · ∪ Vk
em conjuntos esta´veis para G, disjuntos dois a dois, e uma outra
V = U1 ∪ · · · ∪ Ul
em conjuntos esta´veis para H, tambe´m disjuntos dois a dois.
E destas podemos obter uma nova decomposic¸a˜o com componentes Vi∩Uj , que
sa˜o conjuntos esta´veis para G ∨H.
O caso especial H = G da´-nos
χ(G)χ(G) ≥ χ(G ∨G) = χ(Kn) = n.
Esta u´ltima desigualdade podia tambe´m ter sido deduzida a partir do exerc´ıcio
anterior e de dois factos ja´ conhecidos: recorde-se que ω(G) designa o nu´mero
de ve´rtices num clique ma´ximo de G, ou seja, o maior m tal que G tem um
subgrafo isomorfo ao grafo completo Km; para qualquer grafo ω(G) ≤ χ(G) e
ω(G) = α(G). Enta˜o
χ((G)) ≥ n
α(G)
=
n
ω(G)
≥ n
χ(G)
da´-nos a desigualdade no enunciado.
b) A primeira desigualdade e´ consequeˆncia da al´ınea anterior e do caso mais
simples da desigualdade aritme´tica-geome´trica: para quaisquer reais positivos a
e b √
ab ≤ a+ b
2
.
Para a outra desigualdade, usa-se o resultado do exerc´ıcio 27 desta lista: orde-
nando os ve´rtices por valor na˜o crescente do grau, e definindo l como o ı´ndice
para o qual dl+1 < l ≤ dl + 1, temos χ(G) ≤ l.
Para aplicar o mesmo resultado ao grafo complementar G, invertemos a ordem
dos ve´rtices, designando os ve´rtices de G por ui = vn+1−i; temos d′i = d(ui) =
n− 1− dn+1−i e portanto
d′1 ≥ d′2 ≥ · · · ≥ d′n
e portanto, se l′ for o ı´ndice para o qual
d′l′+1 < l
′ ≤ d′l′ + 1
teremos χ(G) ≤ l′. Mas
dl+1 < l ≤ dl+1 =⇒ n+1−dl+1 > n+1−l ≥ n+1−dl−1 =⇒ d′n−l+2 > n+1−l ≥ d′n+1−l+1,
e portanto l′ ≤ n+ 1− l.
Juntando os resultados temos
χ(G) + χ(G) ≤ l + n+ 1− l = n+ 1
30 - Seja G um grafo bipartido com n ve´rtices. Mostrar que G tem, no
ma´ximo, n
2
4 arestas se n e´ par e
n2−1
4 arestas se n e´ ı´mpar.
Resoluc¸a˜o: Seja V = X ∪ Y a partic¸a˜o dos ve´rtices, com |X| = k e |Y | =
n− k. O nu´mero ma´ximo de arestas neste caso e´ k(n− k). Mas esta expressa˜o
toma o valor ma´ximo para k = n/2 se n e´ par, e para k = (n ± 1)/2 se n e´
ı´mpar. Substituindo, obte´m-se o resultado.
31 - Seja G um grafo simples com 2m ve´rtices e mais do que m2 arestas.
Mostrar, por induc¸a˜o em m, que G conte´m um triaˆngulo.
Resoluc¸a˜o: O exerc´ıcio anterior implica que um grafo nas condic¸o˜es do
enunciado na˜o pode ser bipartido e portanto tem que conter algum ciclo de
comprimento ı´mpar. Mas agora verificaremos que tem mesmo que conter um
ciclo de comprimento 3.
O primeiro caso em que as condic¸o˜es se podem verificar e´ com m = 2 e e´ fa´cil
confirmar que se houver mais do que 4 arestas tem que haver um triaˆngulo: pelo
exerc´ıcio anterior, o grafo na˜o pode ser bipartido e portanto tem que conter um
ciclo de comprimento ı´mpar; mas como so´ ha´ 4 ve´rtices esse ciclo so´ pode ser
um triaˆngulo.
Suponhamos agora que a propriedade se verifica para m− 1, ou seja, qualquer
grafo com 2(m−1) ve´rtices e mais do que (m−1)2 arestas conte´m um triaˆngulo.
Seja G um grafo com 2m ve´rtices e m2 + 1 arestas. Sejam x e y dois ve´rtices
adjacentes; temos dois casos: se
d(x) + d(y) > 2m
enta˜o x e y teˆm um ve´rtice adjacente comum u e esses treˆs ve´rtices e as arestas
que os ligam entre si formam um triaˆngulo; para comprovar isso, seja l = d(x) e
j = d(y); enta˜o x tem, ale´m de y, l − 1 ve´rtices adjacentes e, do mesmo modo,
y tem, ale´m de x, j − 1 ve´rtices adjacentes; mas como, ale´m de x e y, G tem
2m− 2 ve´rtices, para que x e y na˜o tivessem um ve´rtice adjacente comum seria
necessa´rio que
l − 1 + j − 1 ≤ 2m− 2.
Passamos enta˜o ao segundo caso: d(x) + d(y) ≤ 2m; nesse caso consideramos o
grafo G−{x, y}, que se obte´m de G eliminando aqueles dois ve´rtices e as arestas
neles incidentes; como x e y sa˜o adjacentes, o nu´mero de arestas incidentes em
x ou y e num ve´rtice de G−{x, y} e´ estritamente menor que 2m; logo este grafo
tem 2(m−1) ve´rtices e mais do que m2 + 1−2m = (m−1)2 arestas e portanto,
pela hipo´tese de induc¸a˜o, conte´m um triaˆngulo, que e´ , naturalmente, tambe´m
um subgrafo de G.
32 - Seja G um grafo simples com n ve´rtices e m arestas. Dados ve´rtices
adjacentes x e y, designamos por xy a aresta incidente em ambos.
a) Mostrar que o nu´mero txy de triaˆngulos de G contendo a aresta xy satisfaz
a desigualdade
d(x) + d(y)− txy ≤ n;
b) Somando sobre todas arestas concluir que o nu´mero total t de triaˆngulos
de G satisfaz
t ≥ m
3n
(
4m− n2)
Sugesta˜o: Usar a desigualdade de Cauchy: dados reais a1, · · · , an tem-se
n∑
i=1
a2i ≥
1
n
(
n∑
i=1
ai
)2
Resoluc¸a˜o: a) txy e´ o nu´mero de ve´rtices que sa˜o simultaneamente adja-
centes a x e a y e que sa˜o portanto contados duas vezes na soma d(x) + d(y);
logo d(x) + d(y) − txy conta, sem repetic¸o˜es, os ve´rtices que sa˜o adjacentes a
algum dos ve´rtices x e y, e que na˜o podem ser mais do que n.
b) Se somarmos d(x) + d(y) ≤ txy +n para todas as arestas vemos que cada
parcela d(v) no lado esquerdo e´ somada exactamente d(v) vezes, pois o grau de
cada ve´rtice e´ contado uma vez por cada aresta nele incidente; por outro lado,
cada triaˆngulo de G e´ contado 3 vezes, uma por cada aresta. Obtemos enta˜o
n∑
i=1
d2(vi) ≤ 3t+ nm.
Aplicando a desigualdade de Cauchy
n∑
i=1
d2(vi) ≥ 1
n
(
n∑
i=1
d(vi)
)2
=
(2m)2
n
=
4m2
n
e portanto
t ≥ 1
3
(
4m2
n
− nm
)
=
m
3n
(
4m− n2) .
Nota: Apresenta-se de seguida uma deduc¸a˜o da desigualdade de Cauchy:
Dados nu´meros reais
a1, a2, · · · , an
considere-se o polino´mio
p(x) =
n∑
i=1
(aix− 1)2;
E´ evidente que p(x) ≥ 0 para todo o x ∈ R; calculando a derivada de p
p′(x) = 2
n∑
i=1
ai(aix− 1) = 2x
n∑
i=1
a2i − 2
n∑
i=1
ai,
deduz-se que p atinge o seu valor mı´nimo, que tem que ser na˜o negativo, para
x =
∑n
i=1 ai∑n
i=1 a
2
i
.
Desenvolvendo os bino´mios temos
p(x) =
n∑
i=1
(a2ix
2 − 2aix+ 1) = x2
n∑
i=1
a2i − 2x
n∑
i=1
ai + n
e substituindo o valor de x conclui-se que(∑n
i=1 ai∑n
i=1 a
2
i
)2 n∑
i=1
a2i − 2
∑n
i=1 ai∑n
i=1 a
2
i
n∑
i=1
ai + n ≥ 0;
mas o lado esquerdo pode simplificar-se e ficamos com
n− (
∑n
i=1 ai)
2∑n
i=1 a
2
i
≥ 0
donde se deduz directamente a desigualdade de Cauchy.33 - Mostrar que um grafo bipartido regular de grau k > 0 tem um empa-
relhamento perfeito.
Resoluc¸a˜o: Seja
V = X ∪ Y, X ∩ Y = ∅
a partic¸a˜o dos ve´rtices. Temos, por o grafo ser bipartido∑
x∈X
d(x) =
∑
y∈Y
d(y)
mas como todos os ve´rtices teˆm grau k, conclu´ımos que k|X| = k|Y | e portanto
os dois lados teˆm o mesmo nu´mero de ve´rtices.
Para provar que o grafo tem um emparelhamento perfeito (cobrindo todos os
ve´rtices), basta portanto mostrar, usando o Teorema de Hall, que existe um
emparelhamento que cobre todos os ve´rtices, por exemplo, de X. Seja enta˜o
X ′ ⊂ X um subconjunto qualquer de ve´rtices e N(X ′) ⊂ Y o conjunto dos seus
ve´rtices adjacentes, isto e´
N(X ′) = {y ∈ Y : ∃x ∈ X ′ x e y sa˜o adjacentes .
Temos que mostrar que |N(X ′)| ≥ |X ′|; ha´ k|X ′| arestas incidentes no conjunto
de ve´rtices de X ′ e portanto ∑
y∈N(X′)
d(y) ≥ k|X ′|;
mas ∑
y∈N(X′)
d(y) = k|N(X ′)|
e portanto temos a desigualdade desejada.
34 - Seja S um conjunto com nm elementos e
S = A1 ∪A2 ∪ · · · ∪An = B1 ∪B2 ∪ · · · ∪Bn
duas partic¸o˜es de S em m− subconjuntos, disjuntos dois a dois, ou seja,
∀1 ≤ i, j ≤ n |Ai| = |Bj | = m;
Mostrar que existe uma permutac¸a˜o pi de {1, 2, · · · , n} tal que
∀i, Ai ∩Bpi(i) 6= ∅.
Sugesta˜o: aplicar o Teorema de Hall a` famı´lia de conjuntos
Si = {1 ≤ j ≤ n : Ai ∩Bj 6= ∅}
Resoluc¸a˜o: Mostramos que dados 1 ≤ i1 < · · · < ik ≤ n, se tem∣∣∣∣∣
k⋃
l=1
Sil
∣∣∣∣∣ ≥ k;
se isso na˜o fosse verdade, a unia˜o ∪kl=1Ail estaria contida em menos que k dos
Bj , o que e´ imposs´ıvel uma vez que
∣∣∪kl=1Ail ∣∣ = km e cada Bj tem igualmente
m elementos.
Mas enta˜o o teorema de Hall garante que a famı´lia de conjuntos {Si : 1 ≤ i ≤ n}
tem um sistema de representantes distintos, ou seja, e´ poss´ıvel escolher para cada
Si um elemento pi(i), tal que
i 6= j =⇒ pi(i) 6= pi(j).
De acordo com a definic¸a˜o dos Si, a permutac¸a˜o pi satisfaz as condic¸o˜es do
enunciado.
35 - Define-se α′(G) como o nu´mero de arestas num emparelhamento ma´ximo
deG. Recorde-se, por outro lado, que β(G) designa o nu´mero mı´nimo de ve´rtices
numa cobertura, ou seja, que incidem em todas as arestas do grafo.
a) Mostrar que β(G) ≥ α′(G);
b) Mostrar que se M for um emparelhamento, C uma cobertura e |M | = |C|
enta˜o M e´ ma´ximo e C e´ mı´nimo;
c) Mostrar que se G for bipartido, se tem β(G) = α′(G).
Resoluc¸a˜o: A al´ınea a) e´ uma consequeˆncia directa das definic¸o˜es: se C
for uma cobertura e M um emparelhamento, cada aresta de M incide em pelo
menos um ve´rtice de C e arestas diferentes de M na˜o podem incidir no mesmo
ve´rtice. E´ portanto poss´ıvel definir uma aplicac¸a˜o injectiva de M em C e temos
|M | ≤ |C|. Como esta desigualdade e´ va´lida para qualisquer cobertura e empa-
relhamento, tem-se a desigualdade do enunciado.
A conclusa˜o de b) e´ agora imediata: se |M | = |C| e M na˜o fosse ma´ximo ou C
na˜o fosse mı´nimo, ter´ıamos um emparelhamento com mais elementos do que os
de uma cobertura.
A al´ınea c) e´ o Teorema de Ko¨nig e Ege´rvary. A demonstrac¸a˜o pode ser feita
a´ custa do Teorema de Berge sobre emparelhamentos e caminhos aumenta´veis:
seja G[X,Y ] um grafo bipartido e suponhamos que X = X1 ∪X2 e Y = Y1 ∪Y2
sa˜o unio˜es disjuntas e que temos um emparelhamento ma´ximo M que liga os
ve´rtices de X1 com os de Y1. De acordo com a al´ınea anterior, basta arranjar-
mos uma cobertura de G[X,Y ] com o mesmo nu´mero de elementos de M .
Chamemos Z ao conjunto de ve´rtices em X1 que podem ser alcanc¸ados por um
caminho M -alternado com in´ıcio em X2. A nossa cobertura vai ser constitu´ıda
pelos ve´rtices em X1\Z e pelos ve´rtices de Y1 emparelhados por M com os de Z.
E´ o´bvio que este conjunto C de ve´rtices tem o nu´mero de elementos desejado;
resta portanto confirmar que se trata de uma cobertura.
As arestas do emparelhamento esta˜o todas cobertas. Ale´m disso, se existir uma
aresta ligando x ∈ X1 com y ∈ Y2 enta˜o x na˜o pertence a Z e portanto aquela
aresta tambe´m esta´ coberta: caso contra´rio existiria um caminho M -alternado
com in´ıcio em X2 terminando em x que poderia ser prolonga´vel ate´ y, criando-se
assim um caminho M -aumenta´vel, o que e´ imposs´ıvel por M ser ma´ximo.
Do mesmo modo, se existir uma aresta entre x ∈ Z e um y ∈ Y1, o par de y por
M em X1 tambe´m pode ser alcanc¸ado por um caminho M -alternado a partir de
X2 e portanto y esta´ no nosso conjunto de ve´rtices e a aresta em questa˜o esta´
coberta. E se existir uma aresta entre x ∈ X2 e y ∈ Y1, o par de y e´ alcanc¸a´vel
por um caminho M -alternado a partir de x, logo pertence a Z e portanto y esta´
em C e a aresta esta´ coberta.
Notamos finalmente que na˜o existem arestas entre ve´rtices de X2 e de Y2, pela
hipo´tese de M ser ma´ximo. As arestas esta˜o portanto todas cobertas.
36 - Os ve´rtices de um grafo G esta˜o divididos em treˆs subconjuntos
A = {a1, a2, a3, a4, a5, a6}
B = {b1, b2, b3, b4}
C = {c1, c2, c3}
Cada ve´rtice de um dos conjuntos e´ adjacente a todos os ve´rtices dos outros
conjuntos, e na˜o ha´ arestas entre ve´rtices do mesmo conjunto.
a) Justificar se G e´ Euleriano;
b) Mostrar que G e´ Hamiltoniano, calculando o nu´mero de caminhos hamil-
tonianos fechados.
Resoluc¸a˜o: G na˜o e´ Euleriano, uma vez que todos os 10 ve´rtices de A ∪B
teˆm grau ı´mpar: cada ve´rtice ai ∈ A tem grau 7, enquanto que os bj ∈ B teˆm
grau 9.
Um caminho fechado hamiltoniano fica definido por um ordenamento c´ıclico dos
ve´rtices em que ve´rtices do mesmo conjunto na˜o fiquem juntos. Para na˜o contar
como diferentes permutac¸o˜es c´ıclicas do mesmo ordenamento, fixamos um dos
ve´rtices na primeira posic¸a˜o.
Podemos portanto alinhar os 6 ai, colocando a1 na primeira posic¸a˜o, de 5!
maneiras poss´ıveis. Os 4 bj e os 3 ck teˆm que ocupar 6 posic¸o˜es ( a seguir a
cada um dos ai); escolhemos uma das 6 posic¸o˜es para colocar um bj e um ck, o
que pode ser feito de
6× 4× 3× 2
modos (o factor 2 refere-se a` escolha da ordem em que o b e o c ficam). Final-
mente ordenamos os restantes 5 ve´rtices de 5! maneiras.
Conclu´ımos que existem
5!× 6× 4× 3× 2× 5! = 6!× 5!× 4!
caminhos hamiltonianos fechados em G.
37 - Se G e´ um grafo com n ve´rtices e sem triaˆngulos, enta˜o
α′(G) = n− χ(G)
onde α′(G) designa o nu´mero de arestas num emparelhamento ma´ximo de G.
Resoluc¸a˜o: A desigualdade
α′(G) ≤ n− χ(G)
e´ va´lida em geral: seja M um emparelhamento ma´ximo. Se atribuirmos uma
cor a cada ve´rtice na˜o coberto por M e uma a cada par de ve´rtices empare-
lhados, obtemos uma colorac¸a˜o admiss´ıvel de G, uma vez que pares de ve´rtices
emparelhados em G na˜o sera˜o adjacentes em G. O conjunto de ve´rtices na˜o
cobertos tem n− 2α′(G) e ha´ α′(G) pares de ve´rtices emparelhados, portanto e´
poss´ıvel colorir G com n− α′(G) cores, ou seja
χ(G) ≤ n− α′(G)
o que e´ equivalente a´ desigualdade do enunciado.
Note-se que o argumento funciona para qualquer emparelhamento e que o caso
em que o emparelhamento e´ ma´ximo nos mostra tambe´m que n−2α′(G) ≤ χ(G)
uma vez que se houvesse um par de ve´rtices na˜o cobertos pelo emparelhamento
adjacentes entre si, poder´ıamos acrescentar essa aresta. Portanto esses ve´rtices
sa˜o um conjunto esta´vel em G, ou seja um clique em G.
Para provar a outra desigualdade, consideremos uma decomposic¸a˜o dos ve´rtices
de G
VG = V1 ∪ · · · ∪ Vk
em conjuntos esta´veis de G, onde k = χ(G). Como G na˜o tem triaˆngulos,
conclu´ımos que cada Vi tem ou 1 ou 2 ve´rtices. Se 0 ≤ j for o nu´mero de
conjuntos da decomposic¸a˜o com apenas um elemento, temos n = j+ 2(k− j) =
2k−j. Podemos formar um emparelhamento em G com os k−j pares de ve´rtices
dos conjuntos restantes, logo
α′(G) ≥ k − j = n− k = n− χ(G).
38 - Dizemos que um ve´rtice v de um grafo G e´ essencial se e´ coberto por
qualquer emparelhamento ma´ximo de G.
a) Dar um exemplo de um grafo sem ve´rtices essenciais.
b) Mostrar queuma a´rvore tem sempre ve´rtices essenciais.
Resoluc¸a˜o: Duas famı´lias de exemplos para a al´ınea a) sa˜o os grafos com-
pletos com um nu´mero ı´mpar de ve´rtices e os ciclos de comprimento ı´mpar,
como se pode verificar facilmente.
Na al´ınea b), considere-se uma folha da a´rvore e o ve´rtice adjacente; se a folha
esta´ coberta pelo emparelhamento, o ve´rtice adjacente tambe´m o esta´, mas se
a folha na˜o e´ coberta por um emparelhamento ma´ximo e´ porque o seu ve´rtice
adjacente ja´ esta´ coberto. Logo os ve´rtices adjacentes a folhas sa˜o sempre es-
senciais.