Hi,

Our teacher asked us this question : "Prove that a simple, connected, bipartite and planar graph verifies : $\displaystyle n \ge f + 2$. From this, find a proof that $\displaystyle K_{3,3}$ is not planar."

Proving that isn't hard, but a friend told me that for n=2 (2 vertex), this fails !

Euler's formula :

$\displaystyle f = e - v + 2 = 1 - 2 + 2 = 1$

And than :

$\displaystyle n \ge f + 2 \Rightarrow 2 \ge 1 + 2 \Rightarrow 2 \ge 3$

That is false !

I tried to read as much as I could about Euler's formula to see if a minimum number of vertex is necessary, but didn't. Unless I am wrong, the proof starts with a single vertex.

Is it simply that what our teacher asked us isn't * always * true or did my friend and I miss something ?

Thanks for