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.

For the second question, your restatement is correct.

  • 1
    $\begingroup$ 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. $\endgroup$ – Joffan Mar 22 '17 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.