# Prove a graph be a planar graph

Q: Prove that a graph in which triangular regions are permitted is planar if and only if $e \le 3v-6$.

This is one of the exercise questions from a discrete mathematics textbook. I feel this questions is wrong. Basically, we can prove that a graph in which triangular regions are permitted is planar implies $e \le 3v-6$. But we cannot prove the converse.

If all the regions are triangular, then we have $3r \le 2e$. So $e+2 =r+v \le \frac23e+v$ after simplification, we get $e\le 3v-6$.

A graph in which triangular regions are permitted. $\Rightarrow e\le 3v-6$

The textbook has another exercise as follows:

Q: Prove that a bipartite graph can only be planar if $e\le 2v-4$.

Basically, this question is equivalent to prove if a bipartite graph is planar, then $e\le 2v-4$. Am I right to say that?

You are correct that the statement "If $e \leq 3v-6$, then the graph is planar" is false. Consider $K_{3,3}$, which satisfies $e = 9 \leq 3(6)-6 = 12 = 3v-6$, but is not planar. I don't read the statement this way, but if the statement is supposed to restrict to graphs that have at least one triangle, it still is not true (consider $K_{3,3}$ plus an edge). Your proof of the converse is fine.
• You could even add two edges to $K_{3,3}$ so that every vertex is on a triangle (3-cycle), and it would still meet the edge count criterion. – Joffan Mar 22 '17 at 15:04