I just took a exam on graph theory and there was one question that I'm not sure if I answered correctly. Is there any tool I can use to check if a graph is planar or not? The graph was a $K_6$ graph where two vertices had an edge missing. So it had the degree sequence $5\,5\,5\,5\,4\,4$.
2026-03-26 18:58:52.1774551532
On
On
Is there a planar graph calculator?
11.9k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
3
There are 3 best solutions below
0
On
Kuratowski' Theorem states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or of K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).
0
On
Your graph $K_6-e$ ($K_6$ minus one edge) contains induced subgraphs isomorphic to $K_5$ and it contains spanning subgraphs isomorphic to $K_{3,3}.$
Hint. It doesn't matter which edge you remove from $K_6,$ the resulting graphs are all isomorphic; all edges are equivalent, because of the symmetry of $K_6.$ So, first find your Kuratowski subgraph of $K_6,$ and then decide which edge of $K_6$ to remove.
There is a whole wikipedia page on planarity testing.
The article contains for example the classic path addition method of Hopcroft and Tarjan. You can find it in the LEDA c++ library.