Гы. Кто сколько времени убил на эту задачку? :О)))
Ответ: Полный двудольный граф, каждая доля в котором состоит из трех вершин НЕ является планарным. Соответствующая теорема доказывается в курсе "теория графов".
По человечески - задача не решаема :О))))