In this video we are going to discuss about Euler's formula or Euler's theorem. First let us see the definition. A connected planar graph G with mod v vertices and mod e edges has exactly mod e minus mod v plus 2 regions.
Here we can apply Euler's formula only on connected planar graph. so what is first let's see what is connected graph so here we can apply this formula on connected planar graph that means that graph should be both connected graph as well as planar graph so first let's see what is connected graph connected graph means from each vertex we should have an edge to any other vertex in the graph here from p we have an edge to q from v we have energy to u from q we have energy to r likewise from s we have energy to r and let us assume that we have one more vertex called z this is not a connected graph why because here this graph contains isolated vertex isolated vertex means from that vertex we don't have an edge to any other vertex here from z we don't have an edge to any other vertex okay So, this is about what is connected graph. Connected graph means from each vertex we should have an edge or path to any other vertex in the graph ok.
And what is a planar graph? Planar graph means if we draw the graph without crossing any edges then it is called as planar graph. So, crossing edges means let me have a graph like this.
Here this edge and this edge these two edges are crossing with each other. Where here in this example the edges are not crossing each other so we can say that this is both connected graph as well as planar graph planar graph means edges are not crossing with each other this edge this edge this edge this edge this edge all the edges are not crossing with each other okay here graph is represented by g vertices are represented by mod v vertices are represented by mod v and the edges are represented by mod e has exactly mod e minus mod v plus 2 region. So what is a region? Region is nothing but a cycle that forms the boundary.
So what is a region? Region means it is a cycle. We know what is a cycle. Cycle means a sequence of edges where the starting vertex and the destination vertex are the same. Here this is the formula mod r is equal to.
So how to calculate number of regions? mod e minus mod v plus 2. R. R we can write like this.
In the right hand side we have 2 here. So let us shift mod d and mod v to the left hand side. So mod v minus mod e plus mod r is equal to 2. So these are the two Euler's formulas.
Let us see two examples in this video. First let us see the first example. Show that the following graph is verified by Euler's theorem.
Here a graph is given like this. So we have to check whether this graph is verified by Euler's formula or not. So let us solve this problem.
So here number of edges are how many edges? First let us calculate number of vertices. Number of vertices are P, Q or 3 vertices. Yes, 4 vertices.
5th vertex, 6th vertex, 7th vertex, 8th vertex. So number of vertices are 8 and number of edges are how many edges are there here? 1, 2, 3, 4. 4 edges next to 5, 6. 6 edges next to 7 8 9 10 edges so number of edges are 10 1 2 3 4 next to 5 6 5 6 7 these are 3 edges so 7 plus 3 10 edges okay uh next we need to calculate number of regions so the formula for number of regions is mod r is equal to mod e minus mod v plus 2 okay so what is mod e Number of edges are 10 minus what is mod v? Number of vertices are 8 plus number of regions plus 2. So, 10 minus 8 means 2. 2 plus 2 means 4. So, the number of regions are 4. Number of regions are 4. Now, let us see what are those regions. Here, this is one region.
This is one region. This is first region R1. Okay.
For space constraints, I am writing here. so r1 is equal to what is a region region means it is a cycle that forms the boundary so here this is a cycle pq uv p so pq uv p so pq uv p okay what this is a cycle why because cycle means a sequence of edges here we have how many edges are there so this is the first edge second edge third edge fourth edges Here we have four edges are there where the starting vertex and destination vertex are the same. Starting vertex is source vertex is pre, destination vertex is also pre.
Ok. So, it is a cycle. Next let us see the second region.
This is the second region. This entire block is the second region. This entire block is the second region.
Ok. So, Q R next from R to W, next from W to R, R to T, T to U, U to Q. Ok. so this is the second region this entire block so first we have to go from q to r next from r2 to r2w so we have to go from r to w next from w to r next from r to t from r to t next from t to u next from u to q okay so q to r r to w next to w to r next r to t t to u u to q so here the number of edges are this is the first edge second inch third edge fourth edge fifth edge sixth edge we can say that degree of r1 is how many edges are there you know what is a degree degree means number of edges associated with that vertex so degree of r1 is how many edges are there that is nothing but the dashes so first edge second edge third edge fourth edge so r1 has four edges likewise r2 has first edge second edge third edge fourth edge fifth edge sixth edge so r2 has six edges next let us see the third region here this is one region and this is another region so we should not take pqr wr so we should not take this region we should not take this region why because this region is nothing but r1 plus r2 only Already R1 is taken, R2 is taken. So, we should not take this entire region.
Okay. P, Q, R, W, R, T, U, V, P. We should not take this region. And the third region is R3.
So, here this is also a cycle. R, S, T. So, from R to S, S to T. Next from T to R.
Okay. Next this entire region, outer region. Outer region is R4.
Outer region is R4. So how to calculate R4? PQ RSTUVP.
So this entire outer region is nothing but R4. Here also we got mod R as 4. So here we have 4 regions. Next let us check the Euler's formula. Let us check Euler's formula.
So how to check Euler's formula? Here we have a formula. Mod V minus mod E plus mod R is equal to 2. So, what is mod V? 8 minus what is mod E? 10 plus what is mod R?
4 is equal to 2. 8 minus 10 means minus 2, minus 2 plus 4 means 2. So, 2 is equal to what is the right hand side? 2. So, left hand side is equal to right hand side. So, we can say that this is verified. Euler's formula is verified.
So, this is about the first example. Now let's see the second example. Find the degree of each region and verify that sum of these degrees is equal to twice the number of edges. And what is the second one? Show that the graph is verified by Euler's formula.
Okay. So a graph is given like this. And this is the Euler's formula.
Mod r is equal to mod e minus mod b plus 2 r. Or we can write it as mod v minus mod e plus mod r is equal to 2 okay so let us solve the problem so here how many vertices are there mod v is equal to number of vertices are 1 2 3 4 5 6 7 so 1 2 3 4 5 6 7 so mod v is equal to 7 and number of edges are 1 2 3 4 5 6. 5, 6, 7, 8, 9. Okay. So, 1, 2, 3, 4, 5, 6, 7, 8, 9. So, 9 edges are there.
Okay. Let us calculate how many regions are there. So, mod r is equal to, what is the formula?
Mod e. Here, what is mod e? 9 minus mod v. What is mod v? 7 plus 2. So, 9 minus 7 means 2. 2 plus 2 means 4. So, number of regions are 4. Here, what we have to do? We have to calculate degree of each region.
In the previous problem there is no need to calculate what is region 1, what is region 2, what is region 3, what is region 4. There is no need to calculate what is R1, what is R2, what is R3, what is R4. But in this problem we have to determine each region. Why? Because we have to find out degree of the each region.
Okay. Let's see what is R1. So this is R1, this path. so this path is nothing but r1 and r2 means this path this path is r2 okay this path is r2 okay so this path okay from p to r r2 t t to s s to q p this is reason two so there is no need to take this entire block so there is no need to take this entire block already r1 is calculated r2 is calculated okay so there is the so there is no need to take this entire block so next what is r3 so this block is nothing but r3 and the entire outer region is nothing but r4 so let us see what is r1 so what is r1 region means it is a cycle which represents the boundary okay what is r1 this block so p 2 t 2 r 2 p so p 2 t t 2 r r 2 p so how many edges are there so first edge second edge third edge so degree of r1 is 3 degree of r1 is 3 next r2 is equal to so this path so p2 r this is a cycle why because here the source vertex and the destination vertex are the same next to p2 r next from r2 t next from t2 s next from s to q next to q to p so p2 r p2r this this this this one so this block this block okay this block so p2r next r2 t t2s s2q q2p so how many edges are there one two three four five so degree of r2 is three next r3 means what is r3 so this path this cycle this cycle so t u s t so t to u u to s s to t okay so how many edges are there first edge second edge third edge degree means the number of edges associated with that vertex here with that region how many edges are there associated with r1 how many edges are there associated with r2 likewise next r4 means the entire outer region the entire outer region so that means p to t t to u you u to v next from v to u u to s likewise the entire problem so pt p2t next from t to u entire outer region next to u2 u2 yeah this is enough yeah we can go from u to v also u to v next from v to u next to u to s next s to q q to p So P2T, T2U, U2V, next V2U, U2S, S2Q, Q2P.
So how many edges are there? 1, 2, 3, 4, 5, 6, 7. So degree is degree of R4 is 7. Now let us calculate sum of all these degrees. So 3 plus 5, 8. 8 plus 3, 11. So 11 plus 7, 8. Sum of all the degrees.
3 plus 5, 8. 8 plus 3, 11. 5 plus 3, 8. 8 plus 3, 11. 11 plus 7, 8. 8. Okay, here what we have to prove and verify sum of these degrees. Sum of these degrees is 18. 18 is equal to twice the number of edges. So, how many edges are there?
9 edges. So, 9 into 2 means 18. So, 18 is equal to 18. So, we can say that this is proved. The sum of... the sum of all the degrees is equal to twice the number of edges the first problem is verified let us see the second one we have to verify euler's formula what is the euler's formula mod v minus mod e plus mod r is equal to 2 mod v minus mod e plus mod r is equal to 2 what is mod v 7 what is mod e 9 plus what is mod r 4 is equal to 2 7 minus 2 means minus 2 Minus 2 plus 4 means 2. So, 2 is equal to 2. 2 is equal to 2. Rhs is equal to RHS.
So, we can say that this graph is verified by Euler's formula. So, this is about Euler's formula or Euler's theorem and two examples regarding that.