onde os trilhos se cruzavam. Nos cruzamentos, o vagão muitas vezes descarrilava e os tijolos
caíam.
Um engenheiro provavelmente teria pensado num modo de reprojetar os cruzamentos.
Turán, sendo um matemático, perguntou-se como deixar o menor número possível de
cruzamentos, redesenhando a disposição dos trilhos. Depois de alguns dias, percebeu que
aquela fábrica em particular tinha cruzamentos desnecessários, mas o problema geral o
intrigou. Com m fornos e n galpões, e presumindo que de cada forno saíssem trilhos para todos
os galpões, a questão é encontrar o número de cruzamentos do grafo bipartido completo Km,n.
Já sabemos um bocado sobre grafos com números muito baixos de cruzamentos (0, 1, 2).
No entanto, sabe-se muito pouco sobre grafos com números de cruzamentos maiores. Na
verdade, os únicos casos em que conhecemos o número de cruzamentos são Kn para n ≤ 10,
Km,n para 3 ≤ m ≤ 6 e grafos Cm × Cn, definidos a seguir, para 3 ≤ m ≤ 6 e m = n = 7.
Os grafos Cm × Cn surgem de “grades retangulares num toro”. A Figura 13.4 ilustra umexemplo, C 7 × C 8. Desenhei o grafo na forma de duas famílias de círculos. Os círculos
“concêntricos” formam 7 cópias de C 8 , e os círculos “radiais” (desenhados como elipses)
formam 8 cópias de C 7. Tais círculos podem ser desenhados na superfície de um toro, onde se
cruzam somente nos pontos pretos. Porém, quando o diagrama é projetado num plano, surgem
outros cruzamentos. De fato, temos 5 cruzamentos para cada um dos 8 círculos verticais,
totalizando 40.
Figura 13.4
O grafo da grade num toro C 7 × C 8 aqui desenhado com 40 cruzamentos. Este número pode ser reduzido?Podemos executar uma construção semelhante com m círculos horizontais e n verticais,
adotando a convenção de que m ≤ n. Assim, cada círculo vertical cruza duas vezes todos os
círculos horizontais, exceto dois deles. Com estes dois — os círculos horizontais de “dentro”
e de “fora” — cruza-se só uma vez, num vértice. Para os demais círculos, um dos cruzamentos
é um verdadeiro cruzamento no toro, daí o vértice; o outro, porém, resulta da tentativa de
desenharmos a imagem no plano. Portanto, cada círculo vertical contribui com m – 2
cruzamentos. Assim, no total, temos (m – 2)n cruzamentos.
Existe a crença geral de que esse é o número mínimo, ou seja, de que o número de