6 punti e 9 linee (tra teoria dei grafi e topologia)

[miles_davis1]

è da un paio di giorni che sto pensando a questo problema:
supponiamo di avere dei punti disposti nel seguente modo
. . .


. . .
bisogna collegare ogni punto della fila inferiore con ogni punto della fila superiore facendo in modo che le linee che collegano i punti non si intersechino in nessun punto. l'idea che mi sono fatto è che non sia possibile, ma non riesco a dimostrarlo. bisogna in qualche modo dimostrare che un punto, dopo al massimo 8 collegamenti (forse anche meno) resta chiuso tra quattro linee. o forse ho imboccato una strada che non mi porta a nulla...
mi aiutate? vi ringrazio.

[Rggb1]

Per un noto risultato (di Eulero, che ne ha trovate tante...) si ha che il grafo bipartito $K_(3,3)$ (quello del tuo esempio) non può essere planare, ovvero come tu dici non si può collegare i tre vertici sopra/sotto tutti fra loro senza incrociare le linee.

[miles_davis1]

mi sapresti dire dove trovare questo risultato? ti ringrazio.

[Rggb1]

Forse ti può bastare uichipedìa
http://it.wikipedia.org/wiki/Grafo_planare
(o meglio ancora http://en.wikipedia.org/wiki/Planar_graph )

Comunque, cerca su Internet "grafo planare" o "planar graph".

[Gi81]

C'è anche un gioco su flashgames che riguarda proprio questo: qui lo trovi