Sorry to post questions so many times…but I'm confused with what use Euler's formula for planar graphs has.
Because, say, $K_4$ the complete graph with 4 vertices is planar after some rearranging of one diagonal edge. But in its "original" state ->☒, it is not.
I thought this formula allows us to judge whether or not a given graph can be isomorphic to a planar graph. But it seems not.
In the original state, it has 5 regions, 4 vertices and 6 edges.
$e+2=r+v$(Euler) then the equation does NOT hold.
However, AFTER rearranging the ☒ so that a diagonal edge does not cross any other edge, then we have 4 regions, hence Euler's formula indeed, holds.
I am wondering…after the rearrangement, by observation, it's more than obvious that the graph is planar, why will we need the equation to verify it?
I thought it would be useful if we can tell planar/non-planar without trial and error and fiddling with the original graph.
But the formula only seems to say "yep you got it planar now" after I've already got the answer…Because it says "no that's not planar" to $K_4$ when it hasn't been altered with.
Then, why is this equation even useful? I don't need to check via the formula when I've gone through the effort to trasnform it to a planar graph and it is extremely obvious that it is.
Am I missing something here? The formula doesn't seem practical in terms of problem solving…
Best Answer
I think you are misunderstanding the definition of planar graphs. It means that you can draw it to the plane without it's edges crossing each other. $K_4$ is for sure a planar graph, for example:
About Euler's formula: You can only use that if you drew a graph to a plane without it's edges crossed. In that case, you can use it to determine whether or not it is a planar graph. In your case, you drew $K_4$ with two edges crossing, that's why it didn't work.
You can use the following inequalities for checking if it is planar graph or not:
Let G be a connected planar simple graph with $n$ vertices, where $n \ge 3$ and m edges. Then $m \le 3n - 6.$ Let G be a connected planar simple graph with $n$ vertices and $m$ edges, and no triangles. Then $m \le 2n - 4 $. For $K_4$, you can see, that $n=4$, $m=6$, and if you check: $6 \le 3*4-6=6$, it works, so $K_4$ must be a planar graph.