Proof: Upper Bound for the Size of Planar Graphs | Graph Theory

The size of a planar graph must be less than or equal to three times the number of vertices minus 6. That is, for a planar graph of order n, size m, and with r regions when imbedded in the plane, m is less than or equal to 3n - 6. We'll prove this upper bound for the size of planar graphs in today's graph theory lesson!

This result follows from Euler's formula for plane graphs. Links to a proof below. A maximal planar graph is a graph that, with the addition of any edges, would become nonplanar. As it turns out, a non planar graph of order n (n greater than 2) will be maximal if it has 3n-6 edges.

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

Follow Wrath of Math on...

[PunmasterSTP]

What's really unbounded is the awesomeness of all these videos! 👍

[College-hlto]

This video helped me find a mistake in my textbook!!

[ChandanSah-unxg]

How can a region have 0 edges on the boundary?

[tame]

These videos are really amazing. Thanks for saving my butt time and time again lol.

[TheWildStatistician]

Hi there awesome teacher! I just can't thank you enough for this quality explanation . Also here is something I deduced, the part of the proof where the external unbounded region must have at least 3 edges "adjacent" to it can be easily proved like this :

Note that we are proving the inequality for SIMPLE planar graphs, i.e no loops nor parallel edges are allowed.

(a) Suppose the exterior region has 0 edges adjacent to it. This clearly can't be the case, since 0 edges cannot enclose the graph as you rightly said.

(b) Suppose the exterior region has 1 edge adjacent to it. This also can't be this case. Note very carefully that if it were the case, then there would have to be a LOOP around the graph starting and ending at some vertex, but that violates the fact that the graph is SIMPLE.

(c) Suppose the exterior region has 2 edges adjacent to it. This also can't be the case. Because if it were the case, then there has to be a parallel edge between two distinct points that go right round the graph! But then again, it violates the fact that the graph is simple!

:D

[koeithleomori]

You said an edge cannot enclose all other edges and regions. But what if it's a big self-loop that encloses everything?

[tesfalegntadesse]

thanks sir for your brief explanation!!
if you are voluntary proof the following problem please...thanks for your cooperation .
Show that a planar graph with n ≥ 3 vertices that does not contain C3 as
a subgraph has at most 2n − 4 edges.

[markkennedy]

Do you mean necessary condition at 15:00 rather than sufficient: If that result isn't the case then the graph is non-planar as you said. Which is what necessary is, isn't it.

[Richh]

If I have a planar graph of a generic city topology, how can I obtain the vertices representating each region? I'm trying to write a program that checks, for each building, in which region that building is contained. I think calculating the dual graph of my graph is useful, but I don't know how merge these informations, in order to solve my problem.

[MrEmanum]

It would reallt help if you do not stand infront of the whiteboard while explaining ...