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

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

life saver

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

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

Very beautiful lecture ♥️

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.

Do Kuratowski and Coloring

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.