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
@@WrathofMath yup mistake was confirmed. In the book it says each edge is counted twice for each region but that's not true since some edges won't be counted twice like the bridge ones
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 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.
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.
What's really unbounded is the awesomeness of all these videos! 👍
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
Thank you for sharing that! I was initially confused on why 2 edges wouldn't work, but that clears things up.
These videos are really amazing. Thanks for saving my butt time and time again lol.
I do my best haha - thanks for watching!
This video helped me find a mistake in my textbook!!
Time for an email to the author!
@@WrathofMath yup mistake was confirmed. In the book it says each edge is counted twice for each region but that's not true since some edges won't be counted twice like the bridge ones
@@College-hl7to That was some great initiative 👍
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.
You said an edge cannot enclose all other edges and regions. But what if it's a big self-loop that encloses everything?
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.
Very beautiful lecture ♥️
Thank you!
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.
Do Kuratowski and Coloring
How can a region have 0 edges on the boundary?
It can't.
#Excelent!
life saver
Glad to help!
It would reallt help if you do not stand infront of the whiteboard while explaining ...
Yes, that does get kind of annoying sometimes, though overall the videos are still great.