Olá Vivi, Vou tentar uma demonstração da impossibilidade aqui, utilizando a fórmula de Euler. O raciocínio se faz por absurdo...
Primeiro, vamos representar o problema no plano. O argumento segue por grafos, portanto vou chamar de vértice um dos 6 pontos: F1, F2, F3, C1, C2, C3 (C de casa, F de fornecedora). As ligações entre algum Ci e algum Fi serão as arestas, e as faces do grafo serão as áreas determinadas por "loops" fechados de vértices, sem nenhuma aresta ou vértice dentro. Intuitivamente falando, uma face é aquela região "limpinha" que as arestas estão cercando. Que tipos de faces podemos ter? Certamente não teremos nenhuma casa ligada diretamente com outra casa, nem uma fornecedora ligada diretamente com outra fornecedora. Então todas as conexões são do tipo Ci -> Fi -> Cj -> ... etc. Um exemplo de face é: F1 -> C1 -> F2 -> C2 (E daí volta para F1.) Neste caso, essa face tem 4 vértices, a saber: F1, C1, F2, C2. Claramente, não podemos ter uma face com menos de 4 vértices, justamente porque não vamos ligar fornecedora com fornecedora nem casa com casa. Uma outra face seria mais longa: F1 -> C1 -> F2 -> C2 -> F3 -> C3 (Volta para F1). Neste caso, temos 6 vértices. Estas são as únicas faces possíveis. O Teorema de Euler no plano diz que Faces + Vértices = Arestas + 2. Temos 6 vértices, e 9 arestas, pois estamos ligando cada uma das 3 casas em 3 fornecedoras. Assim, o Teorema de Euler nos dá: Faces + 6 = 9 + 2 => Faces = 5. Agora, supomos o problema resolvido, e vamos contar de outro modo os vértices. Vimos acima que toda face tem pelo menos 4 vértices. Se temos 5 faces, 5 * 4 = 20 vértices. Mas nesse raciocínio contamos duas vezes cada vértice, pois uma aresta pode ser comum à duas faces distintas, e aí os dois vértices extremos desta aresta foram contados duas vezes. Ainda assim, temos 20 / 2 = 10 vértices, contrariando o fato de só termos 9. Abraço, - Leandro.
