Proof: Upper Bound for the Size of Planar Graphs

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

Рет қаралды 12,301

Wrath of Math

Күн бұрын

Пікірлер: 23

@PunmasterSTP 3 ай бұрын

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

@College-hl7to 6 ай бұрын

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

@WrathofMath 6 ай бұрын

Time for an email to the author!

@College-hl7to 6 ай бұрын

@@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

@PunmasterSTP 3 ай бұрын

@@College-hl7to That was some great initiative 👍

@tame3365 22 күн бұрын

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

@WrathofMath 22 күн бұрын

I do my best haha - thanks for watching!

@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

@PunmasterSTP 3 ай бұрын

Thank you for sharing that! I was initially confused on why 2 edges wouldn't work, but that clears things up.

@tesfalegntadesse3123 Жыл бұрын

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.

@koeithleomori6273 9 ай бұрын

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

@RideR-SAM65 Жыл бұрын

Very beautiful lecture ♥️

@WrathofMath Жыл бұрын

Thank you!

@ChandanSah-un2xg 9 ай бұрын

How can a region have 0 edges on the boundary?

@PunmasterSTP 3 ай бұрын

It can't.

@markkennedy9767 2 жыл бұрын

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.

@ChocolateMilkCultLeader 3 жыл бұрын

Do Kuratowski and Coloring

@Richh777 4 жыл бұрын

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.