Hi,

Our teacher asked us this question : "Prove that a simple, connected, bipartite and planar graph verifies : n \ge f + 2. From this, find a proof that 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 :
f = e - v + 2 = 1 - 2 + 2 = 1

And than :
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