Checking whether a graph is planar

I have to check whether a graph is planar. The given type is

$$ e ≤ 3v − 6 .$$

From Wikipedia:

Note that these theorems provide necessary conditions for planarity that are not sufficient conditions, and therefore can only be used to prove a graph is not planar, not that it is planar. If both theorem 1 and 2 fail, other methods may be used.

I am wondering what should I do to prove that a graph is planar.

Solution 1:

An addition to Douglas S. Stones' post, who mentioned $K_{3,3}$. This graph is bipartite and the shortest length of cycle in this graph is $4$.

For $K_5$ and $K_{3,3}$ the following criteria, which are mentioned in the Wikipedia article on planar graphs, can be used. (Those are precisely the results which you refer to as Theorem 1 and Theorem 2 in your post.)

For a planar graph having $v$ vertices and $e$ edges, the following holds:

• If $v \ge 3$ then $e \le 3v - 6$;
• If $v \ge 3$ and there are no cycles of length $3$, then $e \le 2v - 4$.

(The first one can be used to show that $K_5$ is not planar, the second one can be used for $K_{3,3}$.)

The idea of both proof is similar. And it is based on Euler's formula $$v-e+f=2,$$ which is equivalent to $f=2-v+e$.

Boundary of each face consists of at least $3$ edges. Since every edge belongs to boundaries of two faces, if you add together the lengths of boundaries of all faces, you get precisely $2e$. So we see that
$2e\ge 3f$
$2e\ge 6-3v+3e$
$3v-6\ge e$.

If we, moreover, know that the shortest cycle as at least of length $4$, we get that each boundary must have at least $4$ edges. Hence
$2e\ge 4f$
$2e\ge 8-4v+4e$
$e\ge 4-2v+2e$
$2v-4\ge e$.

Solution 2:

Are you seeking the following result?

Theorem: In a connected simple planar graph with $v$ vertices and $e$ edges, if $v \geq 3$, then $e \leq 3v-6$.

This is typically proved via Euler's Characteristic Formula (e.g. here [pdf warning]); I once set it as a homework question.

This theorem can be used to show e.g. that $K_5$ is non-planar (since it doesn't satisfy $e \leq 3v-6$). But, as Alon Amit commented, the bound $e \leq 3v-6$ can also be satisfied by non-planar graphs, such as $K_{3,3}$ (where more sophisticated arguments need to be used instead).

The most straightforward (human) way of showing a graph is planar is by drawing it in the plane (without crossing edges). Kuratowski's and Wagner's theorems are important results that give necessary and sufficient conditions for planarity.

If you're after particular software, I don't think I could explain it better than in the StackExchange post Shahab mentioned (here).

Solution 3:

Actually a planar graph must be a sparse graph which in case of $K_{3,3}$ means that it contains $9$ edges and $6$ vertices which shows that $K_{3,3}$ is not sparse. By euler verification $K_{3,3}$ does not contain $3$ length cycles or triangles, which means that $e\leq 2v-6$ is not satisfied.