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$.
[Math] planar graph calculator
graph theoryplanar-graphs
Related Solutions
It depends on what you consider a plane drawing to be, but how about something like:
Put a vertex at $(0,0)$ and one at $(1,x)$ for every $x\in\mathbb R$, with a straight edge going between it and $(0,0)$.
Naively this seems to satisfy the requirements of a planar graph drawing: No point lies on two edges (except endpoints), no vertex lies on an edge it is not an endpoint of, every edge is represented by a continuous path between its endpoints.
On the other hand: A problem with this is that if we consider an abstract graph a topological space (with one point per vertex and a copy of the unit interval for each edge, stitched together in the obvious way), then the topology of the above drawing as a subspace of $\mathbb R^2$ is not the same as that of the graph.
Indeed if we define a "plane drawing" of a graph to be a subset of $\mathbb R^2$ which (with the subspace topology) is homeomorphic to the graph, then there can't be any uncountable planar graph, simply because there's no uncountable discrete subset of $\mathbb R^2$ that can be the image of the vertices.
On the other other hand: There are some topological subtleties hidden beneath "stitched together in the obvious way" here. Actually, as soon as there's a node with countable degree the most obvious way of stitching together (resulting in a quotient space) gives something that is not homeomorphic to a straightforward drawing of the graph -- such as a node at $(0,0)$ and one at $(1,n)$ for every $n\in\mathbb N$, with a straight edge to $(0,0)$. This can be fixed, though, by definig the stiching in a slightly more ad-hoc way which gives a different topology on the abstract graph.
Your cases are not exhaustive. You can still have a subgraph of $K_{4,4}$ that is planar and is not a subgraph of $K_{1,7}$, $K_{2,6}$, or $C_8$. Think, for example, of the graph of a cube. Also, you seem to be confusing edges and vertices. The question asks for a graph with $8$ vertices and $13$ edges, but you seem to be talking about graphs with $8$ edges.
While the statement is correct; a planar graph cannot have $8$ vertices and $13$ edges, a better approach is to use Euler's formula. Let $G$ be a planar graph with $8$ vertices and $13$ edges. Without loss of generality, $G$ is connected, so $v + f - e = 2$ (assuming $G$ is connected). This gives us $f = 7$. Now if $G$ is $2$-colorable, then every face has at least $4$ edges on it. So we can "recount" the vertices: we have $7$ faces, each with at least $4$ edges on them, and each edge appears in at most two face. So $e \ge 7 \cdot 4 / 2 = 14$, a contradiction.
Best Answer
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.