Viadutos são caros, mas podem ser inevitáveis

Grafos planares e a necessidade de viadutos, segundo Kuratowski

---

Quatro cidades precisavam ser interligadas, duas a duas, por linhas de trens.


O projeto de conexão entre as $4$ cidades mostrado a seguir foi rejeitado, por exigir a construção de $1$ viaduto:

Em seguida encontrou-se uma opção que eliminava viadutos:

A mesma questão foi colocada para mais cidades:

Nest post vamos:
i) apresentar os correspondentes matemáticos aos esquemas de conexões (grafos) e aos esquemas sem viadutos (grafos planares);
ii) mostrar a resposta de Kuratowski (1896-1980) ao problema de conectar as $5$ cidades e, em geral, a problemas de conexões que possam dispensar viadutos.

---