Non planarity

Question

Kuratowski's second graph is not planar then why it dont contradict for following inequality for checking planarity :

e<=3n-6

=>(e=9)<=3*(n=6)-6

=>9<=12 , which is true

Comments

use this  b/c it not contain triangle. 

Let G be a connected planar simple graph with n vertices and m edges, and no triangles. Then m ≤ 2n - 4.

---

How you derived this inequality?

---

It is not a condition for checking planarity

$COROLLARY$

In any simple, connected planer graph with $f$ regions, $n$ vertices and $e$ edges (e> 2), the following inequalities must hold : 

$e \geq \frac{3}{2}f,$

$e \leq 3n - 6.$

This doesn't mean that any simple graph satisfying this properties is planer.

Answer 1

  K3,3  has 6 vertices and 9 edges, and it is true that 9 ≤ (3 × 6) - 6 = 12. So we cannot use this Corollary to prove that K3,3  is non-planar. We have another Corollary 

Let G be a connected planar simple graph with n vertices and e edges, and no triangles. Then e ≤ 2n - 4.

For graph G with f faces, it follows from the handshaking lemma for planar graph that 2e ≥ 3r  because the degree of each face of a simple graph is at least 3), so r ≤ $\frac{2}{3}$* e

 For graph G with f faces, it follows from the handshaking lemma for planar graphs that 2e ≥ 4r (because the degree of each face of a simple graph without triangles is at least 4), so that r ≤ $\frac{1}{2}$ e.


Proof :   Since   n - e + r = 2 (Euler's formula)
             =>     e -n + 2 = r
                      e - n + 2 ≤ 1/2e
    Hence       e ≤ 2n - 4