1 Coloracoes de grafos

Definicao 1.1 Uma k-coloracao de um grafo G e uma funcao f : V → Sdefinida no conjunto dos vertices de G e com imagem num conjunto S comk elementos (o conjunto das cores), com a propriedade de que se u e v saoadjacentes entao f(u) 6= f(v). Um grafo para o qual existem k-coloracoesdiz-se k-coloravel.

Por definicao, um grafo com lacetes nao admite coloracoes. Por outro lado,um grafo sem lacetes e k-coloravel se e so se o grafo simples que se obtemidentificando todos os conjuntos de arestas paralelas tambem o for. Assim,no que segue, consideraremos apenas grafos simples.

Definicao 1.2 O numero de coloracao de G, χ(G), e o menor k para o qualG e k-coloravel.

Algumas observacoes elementares sobre o numero de coloracao:

Um grafo G de ordem n e k-coloravel para todo o k ≥ n, pelo queχ(G) ≤ n.

χ(G) = max{χ(H) : Hcomponente conexa de G}.

O unico (a menos de isomorfismo) grafo de ordem n com numero decoloracao n e o grafo completo Kn.

χ(G) = 1 se e so se G nao tem arestas; χ(G) = 2 se e so se G e bipartido,ou seja, se existe uma particao dos vertices de G,

V = X ∪ Y ; X ∩ Y = ∅

tal que toda a aresta de G incide num vertice x ∈ X e noutro verticey ∈ Y . Em particular, as arvores bem como os ciclos de comprimentopar tem numero de coloracao 2.

Os ciclos de comprimento ımpar tem numero de coloracao 3.

1

Verificar que χ(G) ≤ k e equivalente a determinar uma particao dosvertices

V = X1 ∪X2 ∪ · · · ∪Xk; Xi ∩Xj = ∅ ∀i 6= j

em conjuntos estaveis, ou seja, tal que para qualquer i ≤ k e para quaisquervertices u, v ∈ Xi, u e v nao sao adjacentes.

Um caso particularmente simples e o dos grafos com χ(G) = 2, ou sejaos grafos cujos vertices sao a uniao disjunta de dois conjuntos estaveis, quecomo referimos sao designados grafos bipartidos.Esses grafos podem ser identificados por uma outra propriedade:

Proposicao 1.3 Um grafo simples e bipartido se e so se nao contem ciclos(caminhos fechados) de comprimento ımpar.

Demonstracao 1.4 Suponhamos que G um grafo bipartido com decomposicaoVG = X ∪ Y ; X ∩ Y = ∅ do conjunto de vertices em conjuntos estaveis. Umciclo e entao forcosamente determinado por uma sequencia de vertices

x1, y1, x2, · · · , xj, yj

onde xi ∈ X e yi ∈ Y , e tem portanto comprimento par 2j.Reciprocamente, suponhamos que G nao contem ciclos de comprimento ımpar.Notamos que basta provar que cada componente conexa de G e um grafo bi-partido, ou seja, basta provar a implicacao para grafos conexos. Escolhemosum vertice qualquer x e definimos dois subconjuntos de vertices

X = {v ∈ VG : dist(x, v) ≡ 0 mod 2}, Y = {v ∈ VG : dist(x, v) ≡ 1 mod 2},

onde dist( , ) designa a distancia entre os v’ertices.E claro que VG e a uniao disjunta de X e Y , uma vez que G e conexo. Restaverificar que cada um desses conjuntos e independente, isto e, que quaisquervertices u, v ∈ X (respectivamente u, v ∈ Y ) sao nao adjacentes.Suponhamos que u, v ∈ X sao adjacentes pela aresta a; existe um caminho C1

de comprimento 2j entre x e u e um caminho C2 de comprimento 2k entrev e x; o passeio fechado C1, a, C2 tem portanto comprimento ımpar e cada

2

aresta nele contida e percorrida ou 1 ou 2 vezes; se eliminarmos nesse passeioas arestas percorridas 2 vezes, ficamos com uma uniao de ciclos (alguns dosquais podem ter comprimento 0, ou seja, serem vertices isolados) dos quaispelo menos um tem comprimento ımpar.

Um minorante obvio para o numero de coloracao de um grafo e dado porω(G), que e a ordem do maior grafo completo que e subgrafo de G (tambemdesignado o maior clique de G).Por outro lado temos tambem χ(G) ≥ |V |/α(G), onde

α(G) = max{|S| : S ⊂ V e estavel}.

Isso decorre de que nenhum dos conjuntos monocromaticos de vertices Xi

pode ter mais do que α(G) elementos; logo,

|V | =∑i≤k

|Xi| ≤ α(G)k

1.1 Algoritmo ganancioso

Um algoritmo simples para colorir um grafo segue a estrategia ”gananciosa”:Dada uma lista de cores c1, c2, · · · e com os vertices ordenados v1, · · · , vn, col-orimos cada vertice por ordem usando a primeira cor que ainda nao foi usadaem nenhum vertice adjacente a ele.

Naturalmente, o resultado depende da ordem dos vertices e embora existasempre uma ordem que conduz a uma coloracao optima (exercıcio), e emgeral difıcil determinar essa ordem antecipadamente.

Exemplo 1.5 Dado m > 1, seja G o grafo bipartido com vertices VG = X∪Yonde

X = {x1, · · · , xm} Y = {y1, · · · , ym}

3

e arestas (xi, yj) para todos os 1 ≤ i, j ≤ m tais que i 6= j.Se tomarmos os vertices na ordem x1, · · · , xm, y1, · · · , ym o algoritmo ganan-cioso da uma coloracao com duas cores e de facto χ(G).Mas se a ordem for x1, y1, · · · , xm, ym o algoritmo ganacioso produz uma col-oracao com m cores.

Entretanto, a analise deste algoritmo permite mostrar que

Proposicao 1.6 : Se G e um grafo conexo, simples, χ(G) ≤ ∆(G) + 1 onde∆(G) designa o maximo dos graus dos vertices de G.

Demonstracao 1.7 De facto, se colorirmos G seguindo a estrategia do al-goritmo descrito atras (para uma ordem qualquer dos vertices) com ∆ + 1cores, quando chegamos a um vertice v, no pior dos casos ele tera ∆ verticesadjacentes, todos coloridos com cores diferentes, e mesmo nesse caso aindatemos uma cor disponıvel.

Pode-se provar um pouco mais:

Teorema 1.8 (Brooks): Se G e um grafo conexo que nao e um grafo completonem um ciclo de ordem ımpar, entao χ(G) ≤ ∆(G).

A aplicacao do algoritmo ganancioso mostra que o importante nao e tantoo grau do vertice a colorir mas sim o numero de vertices adjacentes ja col-oridos. Essa ideia esta na base de um refinamento que podemos introduzirno algoritmo ganancioso, estabelecendo um criterio para a ordenacao dosvertices, e que permite deduzir uma proposicao que pode dar uma melhormajoracao para o numero de coloracao.

Seja n a ordem de G. Fazemos uma ordenacao dos vertices de G que passapor considerar uma sucessao de subgrafos induzidos. Designamos G0 = G

4

e comecamos por escolher um vertice v1 de grau δ(G0); no subgrafo G1 =G0 − {v1}, escolhemos de novo um vertice v2 de grau δ(G1), e assim pordiante: em cada passo temos um subgrafo induzido Gk, escolhemos nele umvertice vk+1 de grau mınimo e definimos Gk+1 = Gk−{vk+1}, ate esgotarmostodos os vertices.Colorimos os vertices de G aplicando o algoritmo ganancioso a ordem inversa

vn, vn−1, · · · , v2, v1;

notamos que, nesta ordem, cada vertice vk e adjacente a no maximo δ(Gk−1)vertices que o precedem na ordem; se d = max{δ(Gk) : 0 ≤ k < n}, podemoscolorir G com d+ 1 cores, uma vez que quando vamos colorir o vertice vk, nopior dos casos existirao d vertices adjacentes ja coloridos, e portanto existedecerto uma cor disponıvel.

A estimativa para χ(G) assim obtida depende certamente das sucessivasescolhas de vertices de grau mınimo nossubgrafos induzidos. Em qualquercaso, temos o seguinte resultado:

Proposicao 1.9 : Seja G um grafo simples e defina-se

d = max{δ(H) : H subgrafo induzido de G}

. Entao tem-se χ(G) ≤ d+ 1.

Existem diversas variantes desta ideia que conduzem a outros tantos resul-tados sobre a majoracao de χ(G). Mas nao existe qualquer formula simplesnem um algoritmo que determine χ(G) em tempo polinomial.

1.2 Coloracao de grafos planares.

Um caso especial que merece mencao e o dos grafos planares. Um dos prob-lemas mais famosos de coloracao de grafos foi o da demonstracao de quequalquer mapa pode ser colorido com quatro ou menos cores. Isso e equiva-lente a afirmacao de que qualquer grafo planar simples e 4-coloravel.

5

Embora as demonstracoes existentes ate hoje deste resultado dependamfortemente de um grande numero de verificacoes so possıveis com a utilizacaode computadores, e muito facil mostrar que um grafo planar simples e 6-coloravel:

Uma consequencia imediata da formula de Euler para grafos planaresconexos simples v − a + f = 2, e que o grau mınimo δ(G) de um grafoplanar simples e menor ou igual a 5: de facto, como vimos, a ≤ 3v − 6, eportanto

δ(G)n ≤∑v∈VG

d(v) = 2a ≤ 6v − 12.

Como isso continua a ser verdade para qualquer subgrafo, a proposicao an-terior garante que G pode ser colorido com 6 cores.

Com um pouco mais de trabalho prova-se o seguinte:

Proposicao 1.10 Um grafo planar, sem lacetes, e 5-coloravel.

Demonstracao 1.11 Por inducao no numero de vertices do grafo. O cason = 1 (e de facto os casos n ≤ 5) sao evidentes. Suponhamos portanto comohipotese de inducao que todos os grafos planares sem lacetes, com menos doque n vertices sao 5-coloraveis, e seja G um grafo nas mesmas condicoes,com n vertices.Sabemos que existe pelo menos um vertice x com grau menor ou igual a 5.Usando a hipotese de inducao, colorimos com 5 cores o grafo G− {x}.Se d(x) < 5 ou d(x) = 5 mas os vertices adjacentes a x nao usam as cincocores, podemos sempre completar a coloracao. Basta portanto considerar ocaso em que os vertices adjacentes ao vertice x que queremos colorir, estaocoloridos com 5 cores; sem perda de generalidade, podemos supor, para sim-plificar a descricao, que as cores 1, 2, 3, 4, 5 estao a colorir, nesta ordem, osvertices adjacentes a x que o rodeiam no sentido dos ponteiros do relogio,numa certa representacao planar do grafo.

6

Consideramos agora o subgrafo de G induzido pelos vertices de cor 1 ou 3;se os vertices x1 e x3, adjacentes a x e coloridos, respectivamente, com ascores 1 e 3, estao em componentes conexas diferentes deste subgrafo, pode-mos trocar as cores 1 e 3 numa dessas componentes, sem violar a regra denao termos vertices adjacentes com a mesma cor; nesse caso, por exemplo overtice x3 passa a ter a cor 1 e a cor 3 fica disponıvel para x.Caso contrario, concluımos que existe um caminho em G, com inıcio em x1

e fim em x3, com cores 1 e 3 alternadas. Na nossa representacao plana, essecaminho limita uma uniao de faces, arestas e vertices de G, contendo porexemplo o vertice x2, colorido com a cor 2; mas entao podemos trocar a cor 2com por exemplo a cor 4 nos vertices que ficam no interior daquele caminho,deixando a cor 2 disponıvel para x.

1.3 Polinomio de coloracao.

Uma abordagem algo diferente ao problema da coloracao de grafos consisteem, dado um grafo G e k cores, procurar determinar quantas coloracoes difer-entes de G com essas cores existem, onde duas coloracoes sao consideradasdiferentes se existe pelo menos um vertice que nao tem a mesma cor nas duascoloracoes. Nao e obrigatorio usar todas as k cores numa coloracao.

Designemos esse numero por p(G, k). E claro que o menor k para o qualp(G, k) > 0 e precisamente χ(G).Se G nao tem arestas, cada um dos seus n vertices pode ser colorido comqualquer uma das k cores, logo nesse caso p(G, k) = kn; por outro lado seG e um grafo completo, todos os vertices tem que ter uma cor diferente ep(Kn, k) = k(k − 1) · · · (k − n+ 1) = n!

(kn

).

Existe uma formula de recorrencia para os numeros p(G, k); recorde-se quedada uma aresta a de G, G \ a e o grafo que se obtem eliminando a em G, eG/a e o grafo que se obtem eliminando a e identificando os vertices incidentes

7

um com o outro. Como se referiu atras, para o efeito de contar coloracoespodemos identificar igualmente as arestas paralelas que possam ser criadas.Tem-se entao

p(G, k) = p(G \ a, k)− p(G/a, k)

De facto, uma k-coloracao de G e igualmente uma k-coloracao de G \ a;por outro lado, uma k-coloracao de G \ a nao induz uma k-coloracao de Gexactamente se os vertices incidentes a a tiverem a mesma cor, e isso acontecese e so se ela e tambem uma k-coloracao de G/a.

Verifica-se que, para um grafo G fixo, p(G, k) e um polinomio na variavelk, o polinomio de coloracao de G, que se determina por aplicacao da formulade recorrencia:

Teorema 1.12 : Dado um grafo sem lacetes G de ordem n, existe um polinomiop(G, x) tal que p(G, k) e o numero de coloracoes de G que se podem fazer us-ando (algumas das) cores 1, 2, · · · , k. Alem disso, se G e simples e a e umaaresta de G, entao

p(G, x) = p(G \ a, x)− p(G/a, x)

O polinomio p(G, x) tem grau n, coeficientes inteiros com sinal alternado,termo principal xn e termo constante nulo.

Demonstracao 1.13 A demonstracao e por inducao no numero m de arestasde G: se m = 0 entao p(G, x) = xn. Se m > 0 e G nao for simples definimosp(G, x) = p(H, x) onde H e o grafo simples associado (que tem menos arestase portanto esta definido por hipotese de inducao). Suponhamos entao que Ge simples; escolhida uma aresta a, ambos os grafos G \ a e G/a tem m − 1arestas e nao tem lacetes. Pela hipotese de inducao existem polinomios

p(G \ a, x) = xn +n−1∑i=1

(−1)n−iaixi, p(G/a, x) =

n−1∑i=1

(−1)n−i−1bixi

8

satisfazendo as hipoteses do teorema.Definimos

p(G, x) = p(G \ a, x)− p(G/a, x)

que se verifica ter as propriedades do enunciado.

Note-se que a recursao pode ser usada quer na forma

p(G, x) = p(G \ a, x)− p(G/a, x)

para chegar eventualmente a uma combinacao linear de polinomios cromaticosde grafos triviais (sem arestas), quer na forma

p(G \ a, x) = p(G, x) + p(G/a, x)

para chegar eventualmente a uma combinacao linear de polinomios cromaticosde grafos completos.Tambem e util para a aplicacao da recorrencia notar que se G tem, por ex-emplo, componentes conexas G1 e G2,

p(G, x) = p(G1, x)p(G2, x).

O exemplo seguinte ilustra estas observacoes

9

Apresentam-se em seguida dois temas relacionados com o problema dacoloracao de grafos.

1.4 O Teorema de Turan

Como vimos, um grafo e p-coloravel, se existe uma particao do conjunto dosvertices V = V1 ∪ · · · ∪ Vp satisfazendo as condicoes

∀i ≤ p Vi 6= ∅ e um conjunto estavel ;

∀i 6= j, Vi ∩ Vj = ∅Um grafo (simples) onde exista uma particao deste tipo chama-se p-partido.Obviamente os grafos p-partidos sao o exemplo mais simples de grafos quenao contem Kp como subgrafo.Vamos agora abordar o problema de outro modo, procurando determinarqual o numero maximo de arestas de um grafo p-partido. A semelhanca dedefinicoes anteriores, um grafo p-partido diz-se completo se para qualquer parde ındices 1 ≤ i, j ≤ p, se tem

i 6= j =⇒ u adjacente a v,∀u ∈ Vi, v ∈ Vj

ou seja se tiver o maior numero possıvel de arestas.

Seja G um grafo p-partido completo e V1, V2 dois dos conjuntos estaveis;suponhamos que |V1| = m e |V2| = m+j com j > 1; o numero de arestas entreestes dois conjuntos de vertices e evidentemente m(m+ j); mas se mudarmosum vertice v de V2 para V1, eliminando as arestas que uniam v a vertices deV1 mas criando uma nova aresta entre v e u para cada vertice u que ficou emV2, verificamos que perdemos m arestas por um lado mas ganhamos m+j−1arestas por outro, ou seja, aumentamos o numero total de arestas do grafo,mantendo a propriedade de este ser p-partido.Concluımos portanto que para obter um grafo de ordem n, p-partido e com omaior numero possıvel de arestas, devemos repartir os vertices em conjuntos

11

tao equilibrados quanto possıvel; dividindo n por p, se n = tp + r, com0 ≤ r < p, temos n = t(p − r) + (t + 1)r e podemos repartir os vertices emp− r conjuntos com t vertices cada e r conjuntos com t+ 1 vertices cada.

Se estes conjuntos forem estaveis e existirem todas as arestas entre verticesde conjuntos diferentes, obtemos um grafo Tp,n, chamado grafo de Turan, cujonumero de arestas e

a(n, p) =(p− 1)n2 − r(p− r)

2p.

A deducao desta formula para o numero de arestas e deixada como exercıcio.Completamos a definicao, pondo Tp,n = Kn se n < p, caso em que naoe possıvel termos um grafo p-partido de ordem n. Note-se alias que para

n ≤ p, temos sempre a(n, p) =

(n

2

)o que justifica a extensao da definicao

(que corresponde a partir o conjunto dos vertices em n conjuntos com umvertice e p− n conjuntos com zero vertices).

Nota 1.14 Note-se que o raciocınio anterior mostrou que Tp,n e, a menosde isomorfismo, o unico grafo p-partido com n vertices e numero maximo dearestas.

O seguinte teorema, devido a Turan diz-nos que os grafos Tp,n nao apenasexemplos de grafos em n vertices que nao contem Kp como subgrafo. Elesconstituem os casos extremos de grafos nessas condicoes:

Teorema 1.15 (Turan) : Se G e um grafo simples de ordem n que naocontem Kp como subgrafo, entao G tem no maximo a(n, p− 1) arestas e estemaximo e atingido se e so se G e isomorfo a Tp−1,n.

Demonstracao 1.16 : Fazemos a prova por inducao em p. O resultado etrivial para p = 2 uma vez que nesse caso G nao tem arestas.Pomos como hipotese de inducao que para qualquer inteiro j < p e qualquer

12

n, um grafo com n vertices e nao contendo Kj como subgrafo, tem no aximoa(n, j− 1) arestas e este maximo e atingido se e so se G e isomorfo a Tj−1,n.Seja entao G um grafo com n vertices que nao contem Kp como subgrafo.Escolhemos um vertice x de grau maximo ∆ e designamos por Y o conjuntodos vertices adjacentes a x e por X o seu complementar (que inclui o propriox).Notamos que as arestas de G se podem decompor em arestas de G[X] (o sub-grafo induzido por esse conjunto de vertices), arestas de G[Y ], e arestas dosubgrafo bipartido G[X, Y ].Por um lado, G[Y ] nao pode conter Kp−1 como subgrafo (caso contrarioterıamos, juntando x e as suas arestas, uma copia de Kp). Portanto, pelahipotese de inducao, o numero de arestas de G[Y ] e menor ou igual a a(∆, p−2) com igualdade se e so G[Y ] e isomorfo a Tp−2,∆.As restantes arestas nao podem ser mais do que (n−∆)∆, uma vez que cadaum dos n − ∆ vertices de X tem grau menor ou igual a ∆. Alem disso, seu, v ∈ X forem adjacentes, entao tem que existir vertices u′, v′ ∈ Y (naonecessariamente distintos) tais que nem u e u′ nem v e v′ sao adjacentes. Ografo que se obtem de G eliminando a aresta u v e criando as arestas uu′ ev v′ tem mais uma aresta que G. Portanto o numero de arestas incidentes emvertices de X atinge aquele valor maximo exactamente se X for um conjuntoestavel (ou seja, se G[X] nao tiver arestas) e cada um dos seus n−∆ verticesfor adjacente a cada um dos ∆ vertices de Y .

Em conclusao, o numero de arestas de G e menor ou igual ao do grafo Hcom os mesmos vertices X ∪ Y , onde o subgrafo induzido H[Y ] e uma copiade Tp−2,∆, Y e um conjunto estavel e x e y sao adjacentes, para todos osx ∈ X e y ∈ Y . Alem disso, o numero de arestas atinge esse valor maximose e so se G e H forem isomorfos.Mas este grafo H e um grafo (p− 1)-partido com n vertices e portanto, comovimos na discussao que levou a definicao dos grafos de Turan, o seu numerode arestas satisfaz |EH | ≤ a(n, p − 1) = |ETp−1,n

| sendo que a igualdade severifica exactamente se H for isomorfo a Tp−1,n.Juntando estas duas conclusoes obtemos o resultado que querıamos provar.

13

O teorema anterior e o metodo da sua demonstracao implicam a seguinteproposicao-algoritmo, cuja demonstracao se deixa como exercıcio.:

Proposicao 1.17 Se G e um grafo simples com n vertices e mais do quea(n, p− 1) arestas, entao G contem um subgrafo isomorfo a Kp que pode serencontrado do seguinte modo: escolhemos um vertice v1 de grau maximo; emseguida escolhemos um vertice v2 de grau maximo no subgrafo de G induzidopelo conjunto de vertices adjacentes a v1, e assim por diante ate ficarmos comum unico vertice vp.O conjunto v1, v2, · · · , vp constitui um clique de ordem p em G.

O Teorema de Turan pode ser usado para demonstrar resultados noutrasareas. Um bom exemplo e o seguinte: se S ⊂ R2 e um conjunto de n pontoscom diametro 1, ou seja,

max{‖x− y‖ : x, y ∈ S} = 1

entao existem no maximo bn2

3 c pares de pontos x, y ∈ S para os quais ‖x −y‖ >

√2

2 .Esse facto pode ser justificado mostrando, por um argumento geometrico,que nao podem existir 4 pontos de S tais que a distancia entre quaisquer doisdeles seja maior que

√2

2 . Consideramos entao o grafo G cujos vertices sao os

pontos de S e em que x, y sao adjacentes se ‖x−y‖ >√

22 ; a conclusao anterior

implica que G nao contem K4 como subgrafo. Pelo Teorema de Turan, G temno maximo a(n, 3) = bn2

3 c arestas.Aquele majorante e de facto optimo: para todo o n > 1 existe um conjuntoS ⊂ R2 de n pontos em que ha exactamente bn2

3 c pares de pontos x, y ∈ Spara os quais ‖x− y‖ >

√2

2 .

Nota 1.18 Os exemplos mais simples e resultados como o Teorema de Turanapodem levar a conviccao de que os parametros χ(G) (numero de coloracao eω(G) (maior subgrafo completo) tem sempre valores proximos. Isso e falso:

14

de facto, dados quaisquer m, k existem grafos G com χ(G) ≥ k e em queo comprimento do menor ciclo (a chamada cintura do grafo ) e ≥ m (eportanto, em particular, ω(G) = 2!).

1.5 A Teoria de Ramsey

Recordemos que um clique de um grafo G e um subgrafo completo, ou sejaum conjunto de vertices adjacentes dois a dois, e que ωG e definido como omaior inteiro m tal que G contem um clique com m vertices.Como se viu, se um subconjunto de vertices S constitui um clique de um grafoG entao S e um conjunto estavel do grafo complementar G e vice-versa.

E natural supor que se um grafo G nao contem um conjunto estavel“grande” entao podera ter um clique “grande”. Esta relacao entre cliquese conjuntos independentes de um grafo (oou, de modo equivalente, entrecliques de G e de G) pode ser descrito em termos de coloracoes com duascores (vermelho e azul) das arestas de grafos completos: podemos identificarG com o grafo cujas arestas sao vermelhas e portanto G com o grafo cujasarestas sao azuis.

Um exemplo elementar daquela relacao e o problema seguinte, incluıdonuma Ficha de exercıcios: dado um grupo de 6 pessoas, existem sempre ou3 que se conhecem entre si ou 3 que sao mutuamente desconhecidas. Asso-ciamos ao problema o grafo K6, cujos vertices identificamos com as pessoas;dados vertices x, y colorimos a aresta entre eles de vermelho se as pessoascorrespondentes se conhecem e de azul caso contrario. A conclusao do enun-ciado traduz-se na afirmacao de que de qualquer coloracao com duas coresdas arestas de K6 resulta sempre um K3 com as arestas todas da mesma cor.Verificamos que e de facto assim: dado um vertice x qualquer, o Princıpio doPombal garante que pelo menos 3 das arestas incidentes em x tem a mesmacor (por exemplo, vermelha); se y1, y2, y3 sao os vertices adjacentes a x poressas arestas entao, ou existe entre dois deles (por exemplo y1 e y2) uma

15

aresta vermelha, e entao o subgrafo induzido por x, y1, y2 tem as arestas to-das vermelhas, ou entao todas arestas entre os yi sao azuis, e temos a mesmaum K3 monocromatico.E facil de verificar que e possıvel colorir as arestas de K5 sem criar qualquerK3 monocromatico, pelo que 6 e o menor inteiro com aquela propriedade.

A generalizacao deste exemplo conduz a seguinte definicao:

Definicao 1.19 Dados p, q > 0, o numero de Ramsey R(p, q) e definido comoo menor inteiro m que satisfaz a propriedade seguinte: qualquer coloracao dasarestas de Km com duas cores (vermelho e azul) produz necessariamente ouum Kp vermelho ou um Kq azul. Ou seja:

R(p, q) = min{m : ∀G grafo simples com |VG| = m, ω(G) ≥ p ∨ α(G) ≥ q},

ou ainda, de modo equivalente,

R(p, q) = min{m : ∀G grafo simples com |VG| = m,ωG ≥ p ∨ ω(G) ≥ q}.

Nota 1.20 Os numeros R(p, q) e o estudo das suas propriedades e aplicacoesfazem parte de uma disciplina matematica, designada Teoria de Ramsey, emhomenagem ao matematico britanico Frank Ramsey (1903-1930).

Algumas observacoes elementares:

• podemos trocar as cores e portanto R(p, q) = R(p, q);

• qualquer grafo com pelo menos um vertice contem K1 como subgrafo,logo, para todos os p, 1, R(p, 1) = R(1, q) = 1;

• se colorirmos as arestas de Kq de vermelho e azul e se houver pelo menosuma aresta vermelha, temos um K2 vermelho; caso contrario temos umKq azul; por outro lado, e possıvel colorir as arestas de Kq−1 todas de azule nao temos nem um Kq azul nem um K2 vermelho; portanto R(2, q) = q.

16

Esta ultima observacao evidencia o tipo de raciocınio envolvido na deter-minacao ou estimativa dos numeros R(p, q): para provar que m < R(p, q)basta arranjar uma coloracao das arestas de Km que nao crie nem um Kp

vermelho nem um Kq azul.Ja para provar que R(p, q) ≤ t, temos que mostrar que qualquer coloracaodas arestas de Kt produz obrigatoriamente ou um Kp vermelho um Kq azul.

Note-se que, a parte os casos simples R(1, q), R(2, q) e o caso R(3, 3),ja calculado, podia na ser obvio que estes numeros existam! Mas tem-se oseguinte teorema:

Teorema 1.21 Os numeros R(p, q) existem para todos os p, q > 0 e satis-fazem a seguinte desigualdade

R(p, q) ≤ R(p− 1, q) +R(p, q − 1).

Alem disso, se ambas as parcelas do lado direito forem pares, tem-se a de-sigualdade estrita.

Demonstracao 1.22 : Fazemos a demonstracao seguindo a formulacao emtermos de coloracoes das arestas de um grafo completo.A demonstracao da primeira parte do Teorema consiste na verificacao de quequalquer coloracao das arestas do grafo completo com R(p−1, q)+R(p, q−1)vertices produz ou um Kp vermelho ou um Kq azul. Isso confirma a existenciade R(p, q) e a majoracao do enunciado. Os numeros de Ramsey sao assimdefinidos por uma forma de recursao. Podemos formalizar esse raciocıniocomo uma prova por inducao em p+q, sendo o caso p+q = 2 trivial: assum-imos, como hipotese de inducao que os R(k, l) existem e tem a propriedadeenunciada, para todos os k, l tais que k + l < p+ q.Seja entao m = R(p − 1, q) + R(p, q − 1) e v um vertice qualquer de Km; vtem R(p − 1, q) + R(p, q − 1) − 1 arestas incidentes e portanto um dos doiscasos tem que se verificar:

• v tem (pelo menos) R(p− 1, q) arestas incidentes vermelhas;

17

• v tem (pelo menos) R(p, q − 1) arestas incidentes azuis.

Suponhamos o primeiro caso; os vertices em que incidem essas arestasazuis induzem um subgrafo completo com R(p − 1, q) vertices, que tem queconter, por definicao, ou um Kp−1 vermelho ou um Kq azul. Neste ultimo casoja temos entao o que querıamos; no outro, esse Kp−1 vermelho, juntamentecom as arestas vermelhas que o ligam a v, forma um Kp vermelho, mais umavez como pretendıamos.O segundo caso e inteiramente semelhante.

Para provar a ultima afirmacao do enunciado, suponhamos que R(p−1, q)e R(p, q−1) sao ambos pares, e tomemos Km com m = R(p−1, q)+R(p, q−1)− 1. Se, para um vertice v qualquer, se verificar uma das condicoes

• v tem (pelo menos) R(p− 1, q) arestas incidentes vermelhas;

• v tem (pelo menos) R(p, q − 1) arestas incidentes azuis.

a demonstracao segue como anteriormente.A unica maneira de isso nao acontecer, uma vez que d(v) = R(p − 1, q) +R(p, q−1)−2, e v ter exactamente R(p−1, q)−1 arestas incidentes vermelhas,e exactamnte R(p, q − 1)− 1 arestas incidentes azuis.Ora isso nao pode acontecer para todos os vertices: caso contrario, somandoo numero de arestas azuis incidentes em todos os R(p−1, q) +R(p, q−1)−1vertices, terıamos que

(R(p, q − 1) +R(p− 1, q)− 1)(R(p, q − 1)− 1)

teria que ser o dobro do numero de arestas azuis, uma vez que cada umadelas seria contada duas vezes, uma por cada vertice incidente; mas isso eimpossıvel porque aquele numero e ımpar.

Exemplo 1.23 Como R(4, 2) = 4 e R(3, 3) = 6 sao ambos pares, concluımosque R(4, 3) < 4 + 6. Fazendo uma coloracao adequada de K8 conclui-se quede facto R(4, 3) = 9: podemos, por exemplo, identificar os vertices de K8 com

18

as classes de congruencia modulo 8 e colorir a aresta i j de vermelho casoi− j ≡ 1 ou 4 mod 8 e de azul caso contrario.Deixa-se como exercıcio verificar que com esta coloracao nao existe nenhumK4 vermelho nem K3 azul.

Exemplo 1.24 Para determinar R(4, 4) comecamos por notar que R(4, 4) ≤R(4, 3) + R(3, 4) = 18. Pode-se, de modo semelhante ao exemplo anterior,verificar que de facto R(4, 4) = 18, descobrindo uma coloracao das arestas deK17 sem nenhum K4 monocromatico: identificamos os vertices de K17 com asclasses de congruencia modulo 17 e colorindo a aresta i j de vermelho caso adiferenca i−j seja um resıduo quadratico modulo 17 e de azul caso contrario.Tal como no exemplo anterior, a verificacao e deixada como exercıcio.

A relativa simplicidade das deducoes feitas nos exemplos anteriores e muitoenganadora: a tabela seguinte contem todos os valores exactos de R(p, q)(com p ≤ q) conhecidos; noutras entradas indicam-se os intervalos nos quaisse sabe estar contido o numero de Ramsey respectivo. Existem estimativasdo mesmo tipo para outros R(p, q) alem dos indicados.

3 4 5 6 7 8 9 10 · · ·3 6 9 14 18 23 28 36 [40, 43] · · ·4 18 25 [35, 41] [49, 61] · · ·5 [43, 49] · · ·...

Podemos obter uma estimativa simples e na recursiva para R(p, q):

Proposicao 1.25 : Para todos os p ≥ 2 e q ≥ 2, tem-se

R(p, q) ≤(p+ q − 2

p− 1

)

19

Demonstracao 1.26 : Por inducao em p + q. Os casos p + q ≤ 5 sao deverificacao imediata:

R(2, 2) = 2 =

(2 + 2− 2

2− 1

); R(2, 3) = 3 =

(2 + 3− 2

2− 1

);

Suponhamos entao que

R(s, t) ≤(s+ t− 2

s− 1

)para todos os s e t tais que s + t < p + q. Pela desigualdade do Teoremaanterior e usando esta hipotese

R(p, q) ≤ R(p−1, q)+R(p, q−1) ≤(p− 1 + q − 2

p− 2

)+

(p+ q − 1− 2

p− 1

)=

(p+ q − 2

p− 1

)onde a ultima igualdade e apenas um caso particular da formula(

m

n

)=

(m− 1

n

)+

(m− 1

n− 1

).

Note-se que, como consequencia da majoracao obtida nesta Proposicao,temos tambem que

R(p, q) ≤ 2p+q−2

e, em particular,R(p, p) ≤ 22p−2.

Por outro lado, tem-se a seguinte estimativa para os numeros de Ramseydiagonais R(p, p):

Teorema 1.27 Para todo o p ≥ 2,

R(p, p) ≥ 2p/2.

Demonstracao 1.28 O caso p = 2 verifica-se directamente, por isso pode-

mos tomar p ≥ 3. Notamos em primeiro lugar que Km tem 2(m2) coloracoes

com duas cores (vermelho e azul, como sempre). Se fixarmos um conjunto

20

de p vertices, existem 2(m2)−(p

2) coloracoes em que o subgrafo Kp induzido poresses vertices e vermelho.Como ha

(mp

)escolhas para esse conjunto de vertices, o numero de coloracoes

de Km com algum Kp vermelho e certamente menor que(m

p

)2(m

2)−(p2);

esta estimativa e alias muito grosseira, pois as coloracoes em que ocorrem,digamos, j Kp vermelhos estao a ser contadas j vezes.Conclu’imos que a proporcao de coloracoes em que ocorre algum Kp vermelhoe menor que (

mp

)2(m

2)−(p2)

2(m2)

=

(m

p

)2−(p

2) <mp

p!2−(p

2);

se m < 2p/2, essa proporcao fica menor que

2p2/2

p!2−

p(p−1)2 =

2p/2

p!<

1

2,

como se deduz facilmente (por exemplo, por inducao).Como a mesma estimativa vale para coloracoes com algum Kp azul, temosque concluir que, com a condicao m < 2p/2, tem que existir coloracoes de Km

que nao tem nenhum Kp monocromatico, e portanto R(p, p) ≥ 2p/2.

O raciocınio feito na demonstracao e um exemplo do chamado metodoprobabilıstico em teoria dos grafos.

A definicao dos numeros de Ramsey para grafos generaliza-se: Dadas kcores c1, · · · , ck, R(t1, · · · , tk) e definido como o menor m tal que qualquercoloracao das arestas de Km com as cores ci contem ou um Kt1 com a cor c1,ou um Kt2 com a cor c2, etc. Prova-se de modo semelhante ao apresentadoacima que estes numeros existem e satisfazem desigualdades do mesmo tipo.Mas o alcance da ideia fundamental da Teoria de Ramsey e muito mais vasto.Em vez de uma tentativa de explicacao, apresentamos, sem pormenores, umoutro resultado, alias anterior a contribuicao do proprio Frank Ramsey para

21

a teoria com o seu nome:Dados inteiros positivos k e r, define-se o numero de van der Waerden(em homenagem ao matematico holandes Bartel Leendert van der Waerden)w(k, r) como o menor m tal que qualquer coloracao dos inteiros 1, 2, · · · ,mcom r cores contem uma progressao aritmetica de comprimento k monocromatica.Prova-se que estes numeros existem de facto mas, se excluirmos os casos triv-iais k ≤ 2, os unicos valores exactos conhecidos sao

w(3, 2) = 9, w(3, 3) = 27, w(3, 4) = 76, w(4, 2) = 35, w(4, 3) = 293, w(5, 2) = 178

Para dar uma ideia da dificuldade da determinacao dos numeros de van derWaerden, o matematico ingles Timothy Gowers provou, em 2011, a seguinteestimativa

w(k, r) ≤ 22r22

k+9

22