Planar Graph

Question

Can minimum degree of a planar graph be $5$? Give some example

Comments

mam, planar graphs are removed from the syllabus

---

Still try to answer

because in 2016 , a question came from this part

---

@Shaik
Has everything related to planar graphs been removed? I mean Euler's planarity theorem and other stuff?

---

Still try to answer

minimum degree is 0, if it is disconnected.... let 2 vertices and 0 edges.

if it is connected then minimum degree=1

i hope you want Maximum degree, in that case also, a star graph is a planar graph with maximum degree = n-1

 

because in 2016 , a question came from this part

mam, can you provide the link?

 

Has everything related to planar graphs been removed?

related to planarity concept is removed.

Euler's circuit or euler's path are in syllabus but Euler's planarity theorem not in the syllabus

---

no, I need a planar graph with min degree 5

is it possible?

---

no... with minimum degree = 4 itself, is not possible

with minimum degree 3 is possible by K₄.

---

@Shaik

chk same question here https://gateoverflow.in/931/gate2003-40

but ans is only 6

---

@Shaik

then ansfor this ques will be B) C) D)

right?

---

@srestha mam for above gate question ans is D only

 

 

---

@srestha can you link to that question in 2016?

---

@Gyanu yes, because that formula I was talking is neceesary for planarity but not sufficient.

@Arjun Sir 

this is one of planarity math came in 2016 https://gateoverflow.in/39553/gate2016-2-03

---

@Gyanu

Here minimum degree cannot be $6$ and maximum degree cannot be anything greater than $6.$

rt?? Because more than $6$, anything gives -ve value for $v.$

---

And if the same question asks for $E\leq 2v-4$, then ans will be $4.$

rt??

---

@srestha mam... 

u r right. Got it. Thnx

---

@srestha mam @Shaik Masthan sir 

planar graph with min degree 4 and 5 are possible. 

---

then u mean any degree planar graph possible?? if we do like this there will be some planar graph with degree 6 or 7 or 8..........

right?

---

@srestha mam 

Planar simple graph with min degree greater than 5 is not possible.  U can draw and check. 

---

@Gyanu

with degree 6 why not possible?

---

Please refer to the derivation of the formula E<= 3V -6

---

@Satbir

that formula about non-planar graph. But doesnot guarantee anything about planar graph.

right?

---

This formula is for connected planar graph and every connected planar graph should follow this.

---

Please note the difference between (p is necessary condition for q)  and (p is sufficient condition for q) and then read the gate 2003 question.

here a graph may also follow E<=3v-6 but it does not mean that it is planar graph but every planar graph should follow the formula.

---

@Satbir

This formula is for connected planar graph and every connected planar graph should follow this.

Chk $Q_{4}$ which is not planar, still follow that formula 

---

Already mentioned in above comment 

a graph may follow E<=3v-6 but it does not mean it is planar.

---

@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

---

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.

Answer 1

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.

Comments

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

---

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.