pertencem a dois conjuntos, cada um com três vértices, e cada vértice de um conjunto está
unido a todos os vértices do outro conjunto. Podemos definir grafos semelhantes quando os
dois conjuntos de vértices possuírem outros números de elementos, não necessariamente
iguais. Se houver m vértices num conjunto e n no outro, o grafo será denotado por Km,n. A
figura mostra K3,3.
Figura 13.1
(a) Grafo com quatro cruzamentos.
(b) O mesmo grafo redesenhado sem cruzamentos.Figura 13.2
Dois grafos básicos não planares.Figura 13.3
Os dois grafos básicos não planares podem ser redesenhados para mostrar que seu número de
cruzamentos é igual a 1.Tanto K 5 como K3,3 possuem número de cruzamentos igual a 1. Nenhum dos dois é planar,o que podemos observar redesenhando as arestas para que se evitem sempre que possível —
assim, percebemos que sempre resta apenas um cruzamento. Veja a Figura 13.3.a e 13.3.b.
O conceito do número de cruzamentos parece ter surgido em 1944, durante a Segunda
Guerra Mundial, enquanto o matemático húngaro Paul Turán trabalhava numa fábrica de tijolos
nos arredores de Budapeste. A fábrica tinha vários fornos onde os tijolos eram assados e
diversos galpões de armazenamento. De cada forno partiam trilhos para todos os galpões. Os
trabalhadores colocavam os tijolos num pequeno vagão e o empurravam pelos trilhos até um
dos galpões, onde os descarregavam. Era uma tarefa relativamente fácil, a não ser nos pontos