11
$\begingroup$

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.

  • 8
    If you just want to prove that a graph is planar, find a planar diagram of the graph. Proving that a graph is non-planar is more difficult, see [Kuratowski's Theorem](http://en.wikipedia.org/wiki/Planar_graph#Kuratowski.27s_and_Wagner.27s_theorems).2011-10-12
  • 4
    There are algorithms for determining whether a given graph is planar - do a websearch for planar and Tarjan - but for smallish graphs Brandon has the right idea: just exhibit a planar diagram of the graph.2011-10-12
  • 2
    If you are interested in a particular graph, perhaps you can describe it in your question.2011-10-12
  • 3
    The graph $K_{3,3}$ has $v=6$ vertices and $e=9$ edges, so it satisfies $e \leq 3v-6$ but it's not planar. I'm not sure what you mean by "the given type is"?2011-10-12
  • 1
    Is the question whether some or all graphs satisfying $e \le 3v-6$ are planar?2011-10-12
  • 1
    See this related (thread)[http://stackoverflow.com/questions/1854711/how-to-check-if-a-graph-is-a-planar-graph-or-not].2011-10-16

4 Answers 4