Graphe biparti

Dans le livre Graphs and Applications : An introductory Approach de Joan M. Aldous et Robin J.Wilson (springer) on propose la solution suivante :

Le graphe est représenté comme dans le premier fichier joint.
Le raisonnement est le suivant :
$K_{3,3}$ possède un cycle de longueur $6$ (le cycle $1-6-2-5-3-4-1$). Dans un plan on peut dessiner ce cycle comme un hexagone. Il manque alors $3$ arêtes : $1-5$, $2-4$ et $3-6$.
On ne peut tracer qu'une seule arête à l'intérieur de l'hexagone, à partir de $2$ elles se croisent (voir le second fichier) . On remarque la même chose si on décide de tracer les arêtes à l'extérieur de l'hexagone (faire le dessin).
Par conséquent il est impossible de tracer les trois arêtes manquantes sans créer de croisement et le graphe n'est donc pas planaire.

Je ne sais pas si on peut formaliser plus mais c'est bien l'idée.

Une façon que je trouve visuellement satisfaisante mais pas très propre théoriquement . On considère cinq des sommets $a_1,a_2,b_1,b_2,b_3$ et les arêtes reliant ces sommets . On a nécessairement l'une des trois conditions qui est vérifiée :
$b_1$ est à l'intérieur du cycle $a_1b_2a_2b_3$
$b_2$ est à l'intérieur du cycle $a_1b_1a_2b_3$
$b_3$ est à l'intérieur du cycle $a_1b_1a_2b_2$

Si par exemple la deuxième condition est vérifiée ( voir figure jointe ) . Alors quelle que soit la position de $a_3$ , il ne peut être relié à l'un des $b_i$ sans traverser une frontière :

1°) si $a_3$ est dans la région 1 , il ne peut être relié à $b_3$ .
2°) si $a_3$ est dans la région 2 , il ne peut être relié à $b_1$ .
3°) si $a_3$ est dans la région 3 , il ne peut être relié à $b_2$ .

Domi