Questo problema e' molto difficile e la soluzione che conosco io e' abbastanza lunga e complessa ma non richiede la conoscenza di matematica superiore per essere compresa.

Innanzitutto le cattive notizie. Non esiste nessuna soluzione, o, parlando in termini piu' astratti, non c'e' modo di connettere sul piano ciascuno di un gruppo di tre punti con tutti i punti di un altro gruppo di tre punti senza incrociare delle linee. Questo tipo di schema di connessioni (due gruppi di tre punti con tutte le possibili connessioni fra punti dei due gruppi) si chiama in teoria dei grafi K_3,3 e la proprieta' di un grafo di poter essere disegnato sul piano senza incrociare le linee si chiama planarita'.

Con queste definizioni la soluzione sara' una dimostrazione che K_3,3 non e' un grafo planare.

Se consideriamo un generico grafo connesso (ovvero tale che ogni punto sia raggiungibile da qualunque altro punto muovendosi lungo le linee del grafo) sul piano (ovvero disegnato sul piano in modo che non ci siano incroci di linee) e chiamiamo V il numero di punti (vertex), E il numero delle linee (edge) e F il numero delle facce (face - zone in cui le linee del grafo suddividono il piano contanto anche l'esterno) allora V - E + F vale sempre 2.

Un esempio della formula di Eulero: in questo caso V=5, E=10 e F=5. Come per tutti i grafi planari connessi abbiamo V-E+F = 7-10+5 = 2.

Per capire perche' questa formula vale sempre per un grafo planare connesso consideriamo il grafo composto da un solo vertice sul piano. In questo caso la formula ovviamente vale essendo V=1, E=0 e F=1 (l'unica faccia e' l'intero piano) e quindi V-E+F=1-0+1=2. A questo punto e' semplice notare che qualunque grafo planare connesso e' ottenibile partendo da questo grafo elementare tramite due tipi di operazione: l'aggiunta di un altro vertice connesso ad uno esistente tramite una nuova linea oppure l'aggiunta di una linea fra due punti gia' presenti.

Entrambe queste operazioni pero' non cambiano il risultato della formula visto che operazioni del primo tipo incrementano di uno sia V che E mentre operazioni del secondo tipo aggiungono una linea e chiudono un'area e quindi aumentano sia E che F. Nessuna di queste operazioni quindi cambia il totale V-E+F.

Consderiamo un grafo planare e disegnamo due puntini vicino al punto medio di ogni linea (uno per parte). In questo modo noi abbiamo disegnato 2E punti ma guardando dal punto di vista delle facce si nota che ogni faccia' avra' ricevuto tanti punti quante sono le linee che ne definiscono il perimetro.

Disegnare due punti per ogni linea rende evidente che la somma del numero di linee che compongono il perimetro delle facce vale esattamente il doppio del numero delle linee.

Noi possiamo anche notare che un qualunque ipotetico disegno sul piano di K_3,3 non puo' contenere facce il cui perimetro sia formato da sole tre linee (in altre parole non possono essere presenti triangoli). Per vedere il motivo notiamo che un triangolo significa la presenza di tre punti ciascuno connesso agli altri due e traducendo questo nel linguaggio originale del problema si vede che questo implicherebbe la presenza di una connessione fra due case o fra due punti di distribuzione.

Se non ci sono triangoli, connessioni multiple oppure punti collegati a se stessi (loop) questo significa anche che la somma del numero dei lati delle facce non puo' essere inferiore a 4F visto che non possono esistere facce con meno di 4 lati.

A questo punto e' possibile mettere assieme le considerazioni espresse precedentemente e ricavarne come conclusione che non puo' esistere un disegno di K_3,3 sul piano senza che siano presenti incroci di linee.

V - E + F = 2      // Formula di Eulero
2V - 2E + 2F = 4   // Moltiplicata per 2
2E >= 4F           // Non ci sono triangoli
E >= 2F            // Divisa per 2
2V - 2E + E >= 4   // Sostituzione di 2F con E
2V - E >= 4        // Semplificazione
2V - 4 >= E        // Esplicitazione di E

I calcoli precedenti e la condizione finale descritta valgono per qualunque grafo planare connesso senza triangoli, connessioni multiple o loop. Se sostituiamo a V il valore che noi abbiamo per K_3,3 (ovvero 6) allora otteniamo una condizione che limita il numero massimo di linee a 2x6-4=8.

Questo significa che K_3,3 (che e' connesso e non ha triangoli, connessioni multiple o loop) non puo' essere planare perche' ha troppe linee; per essere precisi ha una linea in piu' del massimo consentito di 8.

Con K_3,3 questo e' anche particolarmente frustrante in quanto e' semplice disegnare sul piano tutte le connessioni tranne una; in altri termini K_3,3 e' planare una volta che venga rimossa una linea (vedi figura).

Un disegno sul piano di K33 una volta che sia stata rimossa una connessione (la casa centrale non ha elettricita').