[Discrete Mathematics] Euler's Theorem

We introduce Euler's Theorem in graph theory and prove it.
Visit our website: bit.ly/1zBPlvm
Subscribe on TH-cam: bit.ly/1vWiRxW
-Playlists-
Discrete Mathematics 1: • Discrete Math (Sets, L...
Discrete Mathematics 2: • Discrete Math (Countin...
-Recommended Textbooks-
Discrete and Combinatorial Mathematics (Grimaldi): amzn.to/2T0iC53
Discrete Mathematics (Johnsonbaugh): amzn.to/2Hh7H41
Discrete Mathematics and Its Applications (Rosen): amzn.to/3lUgrMI
Book of Proof (Hammack): amzn.to/35eEbVgLike us on Facebook: on. 1vWwDRc
Submit your questions on Reddit: bit.ly/1GwZZrP
We introduce Euler's Theorem and two corollaries related to Planar Graphs.
Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.

[@Simon_Larsson]

I got a bit confused during the proof. In the part where the graphs are disconnected the equation doesn't add up. So i checked and you should put Eg=Eh1+Eh2+1. Otherwise you get in the example 11=5+5-1=9 and thats not true.
Thanks for all the lectures they are awesome!

[@mrvargarobert]

+Simon Larsson You are right. Then, the last equation reads Vg - Eg + rG = Vh1 - Eh1 + Rh1 + Vh2 - Eh2 + Rh2 - 2 = 2 + 2 - 2 = 2. I think it would be clearer if instead of deleting an edge you would merge two vertices. This way, you are left with one component with one less vertex, one less edge and the same number of regions, so the Euler characteristic is the same.

[@rhetorical_annihilation]

@@mrvargarobert With mathematical induction, you are supposed to assume the general case is true and then check to see if you can prove the k+1 case is also true. I think its unusual that you went about this by taking away an edge. I would have thought adding an edge would make more sense.

[@alitarikdogan5825]

+1

[@ephoenix7]

You explain things well

[@emperor8716]

2:20 then what's the point of euler's theorem? if it has to be a planar embedding for the theorem to be true, then we can just conclude that it is planar from looking at the graph...

[@jay_ndimande]

you are better than my math lecturer 😌.

[@JuliusBrainz]

The part with two outer regions probably comes from additional axioms. Otherwise, if a disconnected graph is considered, all the outer regions of each subset should merge into one outer region, which makes much more sense; i.e. the assumptions about outer regions in graph theory are not intuitive.

[@jneff7564]

Youre the man

[@Laughbankrip]

You have just saved my grade man

[@oidbio2565]

You should fix your induction proof of Euler's Theorem. you know vH - eH + rH = 2....want vG - eG + rG = 2

[@hchen31]

I don't understand the second part of the proof (disconnected). Can anyone help? 10:19 I got Vh1+Vh2 = Vg; Eh1+Eh2+1 = Eg; Rh1+Rh2-1 = Rg. We know Vg-Eg+Rg = 2, so Vh1+Vh2 - (Eh1+Eh2+1) + (Rh1+Rh2-1) = Vh1+Vh2 - Eh1 - Eh2 -1 + Rh1+Rh2-1 = Vh1+Vh2 - Eh1 - Eh2 + Rh1+ Rh2 - 2 = 2 If so, then Vh1+Vh2 - Eh1 - Eh2 -1 + Rh1+Rh2-1 = Vh1+Vh2 - Eh1 - Eh2 + Rh1+ Rh2 should be 4?

[@dipankarpurecha5564]

The equation at 16:34 doesn't seem to hold when the graph has 2 vertices and an edge between them (K1,1), since r=1, e=1 but 4*1 is not lesser or equal to 2*1
Am I missing something?

[@Saberthroat]

K1,1 is not planar (specifically working with connected planar graphs as stated in Euler's theorem at the start, the rest of the theorems are technically corollaries of Euler's theorem I believe).
A connected planar graph has v >= 3

[@albertbokor6643]

At 8:15, shouldn't we add instead of subtract?

[@HaakonJacobsen]

Old comment, but answer still holds. Assuming you mean what happens after 8:15 with calculating regions. We subtract since we go from 5 regions before the edge is removed to counting h1 = 3 regions, and h2 = 3 regions giving us 6 regions. Here we have counted the infinite region (the region that is outside the graph) in h1 and h2 twice, since we added them in both. If we had done what I think you are suggesting, which is saying the regions in h1 = 2 and h2 = 2 giving us 4, and THEN add 1 to get 5, it would be wrong. Because when you say regions in H1 you have to count the region outside the graph. Same goes for H2, you have to count the region outside that graph as well. Since they are the same region we remove one. The answer 5 = (2+2+1) would be right, but you can't say the regions in h1 and h2 is 2, that would be wrong since they are 3. So 5 = (3 + 3 - 1).

[@user-yb2hq3km7h]

in 17:22 i don't get how 2r

[@user-uk6zh6lr1m]

εξηγει καποια πραγματα ελπιζω να βοηθησει

[@tuana9004]

Can somebody please explain to me the part in the proof where we say e

[@commenting000]

2 years late. That's just telling you that the graphs that have planar embeddings (no edges intersecting at any other place other than their ends) with edges

[@markborz7000]

You really messed up with the Euler theorem. The arguments are wrong. E.g.: You want to prove G, given H by induction. You did it the other way round.
And the argument for counting faces in case of disconnected graphs into H1 and H2 are also totally wrong.
Removing the connecting edge gives ONE outer face instead of two before. Because to count regions one has to cut along all edges and see what's left. Cutting along that one connecting edge is topologically like opening a hole, which is the additional region to the outer space. So by removing that connecting edge reduces faces from 2 to 1 (because the hole is gone). Since the edges also reduce by 1, nothing changes and the (Euler) formula for G is the same as H, with H given by induction. QED.

[@daviduzumaki]

" the argument for counting faces in case of disconnected graphs into H1 and H2 are also totally wrong."
no it's not.
it's the same as counting the cardinality of sets that have an intersection(i.e inclusion-exlcusion principle) |S1| + |S2| - |S1 ∩ S2|
so h1+h2 is 2 regions/faces -1 = 1 face/region in total

[@gor3947]

oler chi elera esh

[@gor3947]

lav ches ara?