Now we'll see what Euler's Formula gives us.

First I want to say that every face has at least three edges,

for example this face has five edges.

This face has three edges and this face has four edges.

There is no way to draw a face with two or one edges.

And also every edge belongs either to two or one faces.

For example, this edge belongs to two faces.

This edge belongs to two faces.

But this one belongs only to one face.

Every edge belongs either to one or two faces.

What can I conclude from this?

Let's consider a planar graph on at least three vertices,

and we know that each face has at least three edges.

We also know that each edge belongs to at most two faces.

Now let's count the number of pairs,

face and edge such that this edge belongs to this face.

First we know that the number of such pairs is at least three times the number of faces,

because each face has at least three edges.

On the other hand,

we know that the number of such pairs is at most two times the number of edges,

because each edge belongs to at most two faces.

This gives us that f is the number of faces,

in a planar graph is at most 2e/3,

where e is the number of edges.

Recall Euler's formula, v - e + f = 2.

And now we also know that f is at most 2e/3.

I want to say that this gives us the full of it.

Every connected planar graph on at least three vertices has at most 3v - 6 edges.

Let's go and prove it.

From Euler's formula now that 2 = v - e + f,

which as we now know is upper bounded by v - e + 2e/3,

which is v - e/3.

Now we multiply this inequality by three and we get is that,

the number of edges e is at most 3v - 6.

Also we can conclude that every connected planar graph

has a vertex of degree at most five,

because if that wasn't the case,

if there was a planar graph where degree of each vertex is at least six,

then the number of edges in such a graph would be the sum of the degrees divided by two,

which is at least 3v.

But we know that e must be at most 3v - 6 or contradiction.

So now we know that every planar graph has a vertex of degree at most five,

and we also know that in a planar connected graph on at least the vertices,

the number of edges is at most 3v - 6.

Now we can say that the complete graph on five vertices is non-planar.

That is we cannot connect five subway stations

without crossing subway lines.

This is why.

We get five vertices and ten edges in the complete graph of five vertices.

But in the planar graph, with 10 edges, we would have

3v - 6 greater than 10.

But in the full graph, in the complete graph of five vertices 3v - 6 is 9.

Which is less than 10.

So this graph is not planar.

There is no way to draw the complete graph on five vertices without crossing edges.

But do you think we can connect

three houses with three utilities without crossing connections?

Do you think the complete bipartite graph on three and two vertices is planar?

We know that in this graph we got six vertices and nine edges.

And this does satisfy the inequality e is at most 3v - 6.

So we can't yet conclude that this graph is not planar.

Let's see what we can say about bipartite planar graphs.

We already know know that bipartite graphs don't have cycles of odd length;

which means they can't have a face on three edges.

So every face in a bipartite planar graph has at least four edges.

And now if again we compute the number of pairs,

edge and the face,

such that this edge belongs to the face,

then we would say that the number of pairs is at least four times the number of faces.

And again it's at most two times the number of edges,

because each edge belongs to either one or two faces.

From this we conclude that,

in a bipartite planar graph,

f is at most e/2.

Now from Euler's formula v - e + f = 2,

and this recent observation f is at most e/2,

we conclude that in a bipartite graph on at least four vertex in

a bipartite connected planar graph on at least four vertices,

e is at most 2v - 4.

That's how it's showed.

Two is v - e + f,

by Euler's formula which in a connected bipartite planar graph is at most v - e + e/2.

That is v - e/2,

we multiply it by two and we get that the number of edges is

at most two times the number of vertices minus four.

Now let's look at this complete bipartite graph on three and three vertices.

It has six vertices, nine edges.

So the number of edges,

nine is not less than or equal to 2v - 4 which is 8.

So this graph is not bipartite.

There is no way to draw it in the plane without crossing edges.