You could not solve either problem.
What’s interesting is that those two problems are the ONLY ones that cannot be solved.
This is the
result:
A graph is nonplanar
if and only if it contains as subgraphs either the utility graph or the complete five node graph.