0 votes 0 votes Can minimum degree of a planar graph be $5$? Give some example Graph Theory graph-theory graph-planarity + – srestha asked Oct 22, 2018 srestha 1.7k views answer comment Share Follow See all 25 Comments See all 25 25 Comments reply Show 22 previous comments Satbir commented Jun 24, 2019 reply Follow Share Already mentioned in above comment a graph may follow E<=3v-6 but it does not mean it is planar. 1 votes 1 votes srestha commented Jun 24, 2019 reply Follow Share @Satbir ur 2nd graph is wrong. Plz remove it. It has many vertex with degree 3. Only @Gyanu graph is correct. More over graph neednot to be complete. But yes degree 5 graph is possible and degree 6 graph not possible 0 votes 0 votes Satbir commented Jun 24, 2019 reply Follow Share please note what you have asked in question Can minimum degree of a planar graph be 5? Give some example I have tried to provide various cases using examples just to clear confusion. First graph is a complete graph and planar graph and min degree is 3... complete graph with degree >3 is not possible. Second graph is simple graph and planar graph this i have used to show that degree in planar graph (not degree of planar graph ) can be >=5 just to avoid confusion regarding the statement which you are saying degree 5 graph is possible and degree 6 graph not possible graph with min degree 5 is possible and min degree 6 is not possible.your statement is also correct. I have used the example just to show that degree of graph and degree of vertex are different things Third graph is regular graph and planar graph and has min degree is 5. This is the main answer. All the three satisfy E<=3v-6 since they are planar graph If you still think it is not required then i will remove it. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes For a complete planar graph Minimum degree of the graph could not be $5$. It could be $3$ at max. However, the degree of one of the vertex in planar graph can be $5$ Also we can have a regular planar graph with degree $5$ at max. Satbir answered Jun 21, 2019 • edited Jun 23, 2019 by Satbir Satbir comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented Jun 22, 2019 reply Follow Share @Satbir if we do like this, then a planar graph with degree 6 also possible. rt?? But according to them(GATE-2003 question) planar graph with degree 5 possible, but planar graph with degree 6 not possible. Here my question was , why?? 0 votes 0 votes Satbir commented Jun 22, 2019 reply Follow Share Yes, if we place a vertex in the middle and add connect it to other vertex such that edges do not intersect then we can have degree 7 also. similarly we can have any number of degree for a vertex. Please note that they are asking for min degree of G in gate 2003. 0 votes 0 votes Please log in or register to add a comment.