3 votes 3 votes Consider 11-regular connected graph of order 8. How many regions are there in planar embedding? Graph Theory graph-theory + – Tuhin Dutta asked Dec 10, 2017 Tuhin Dutta 1.9k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Shubhanshu commented Dec 10, 2017 reply Follow Share 38 ?? 0 votes 0 votes Rishabh Jain 1 commented Dec 10, 2017 reply Follow Share Can you explain how you got 38? 0 votes 0 votes abhishek tiwary commented Dec 10, 2017 i edited by abhishek tiwary Dec 10, 2017 reply Follow Share 38?? R=11*4-8+2=38?? 0 votes 0 votes Shubhanshu commented Dec 10, 2017 reply Follow Share Deg of each vertex = 11 Number of edges = 88, number of vertex = 8, number of edges = sum of degree of each vertex /2 ->> 8*11/2 = 44. V = 8 E = 44 Now, applying Euler's formula for planar graph. --> V - E + r = 2 8 - 44 + r = 2 r = 36 + 2 r = 38. 3 votes 3 votes pawan kumarln commented Dec 10, 2017 reply Follow Share #vertices = order of graph=8 #edges in 11-regular connected graph of order 8 = (11*8)/2 = 44 (as #edges in k-regular graph = (n*k) / 2) #region=e-n+2=44-8+2=38 0 votes 0 votes Rishabh Gupta 2 commented Jan 15, 2018 reply Follow Share @Shubhanshu Number of vertices = 8. So how can the degree of each vertex be 11 ??? With 8 vertices, we can have a max degree of 7. Right? Please tell me if I am missing something. _/\_ 1 votes 1 votes Rishabh Jain 1 commented Jan 15, 2018 reply Follow Share it is not a simply connected graph. 0 votes 0 votes Shubhanshu commented Jan 15, 2018 reply Follow Share @Rishabh Gupta 2 it is given in the question that degree of each vertex is 11, it is not given in the question directly that degree of each vertex is 11, but the above graph is "11-regular graph" which means the degree of each vertex is 11. And then the remaining calculation is given in the above comment. 0 votes 0 votes Rishabh Gupta 2 commented Jan 15, 2018 reply Follow Share @Shubhanshu Yes I understood that part. But my doubt is if we have say n vertices, then what is the max degree possible for any vertex?? Answer this in general (do not relate it to this question) I think max degree a vertex can have is n-1. Since a vertex can atmost connect to all other vertices. So, now coming to the question. How can a graph with only 8 vertices, there can be any vertex with degree 11 ? 1 votes 1 votes Shubhanshu commented Jan 15, 2018 reply Follow Share Yes, @Rishabh Gupta 2 I got your point. It means this question is meaningless. Thanks. 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes E= n*k/2 =8*11/2 =44 V=8 R=E-V+2 =44-8+2 =38 mohitbawankar answered Dec 10, 2017 mohitbawankar comment Share Follow See all 0 reply Please log in or register to add a comment.