edited by
15,480 views
65 votes
65 votes

A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid  - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be 

  1. $3$
  2. $4$
  3. $5$
  4. $6$
edited by

9 Answers

3 votes
3 votes

Given equation is true for a planar graph.

In planar graph, e<=3*v-6.-----(i)

This follows from the fact that every face has degree at least 3 so 2E = Σci ≥ 3F which implies that F ≤ 2/3 E. Plugging this into Euler’s formula yields the desired result.

https://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/lecture-notes/MITHFH_lecturenotes_1.pdf

And also if G is planar graph then G does not have  vertex of degree  exceeding 5.

Proof:-

suppose degree of all vertices is 6 then,

2e=6*v

e=3v,but it contradict the given statement.

so planar graph can't have vertex of degree grater than 5.

3 votes
3 votes

We know the relation $minDeg\leq \frac{2e}{v}\leq maxDeg$

Substitute e=3v-6

Then  $min-deg\leq \frac{2e}{v}$ == $minDeg\leq \frac{6v-12}{v}$

=> $v*min-deg\leq 6v-12 $

==> $12\leq v(6-minDeg)$

SO, $6-minDeg$ must +ve inorder to Rhs be  greater

Then 3,4,5 possible BUT 6 cannot be.

So ans is 6==>option D 

2 votes
2 votes
if G has 1 or 2 vertices , the result is true . if G has at least three vertices ,

now given is e<=3v-6 <->2e<=6v-12. now if the degree of every vertex were atleast six , then by handshaking theram 2e=summation of degree of all vertices. so from here we can conclude that 2e>=6v , but given 2e<=6v-12  it means there is contradiction , so we must have at least 1 vertex of of degree not greater than 5 (it is also corollary for planner graph ) it means minimum degree can not be 6 , minimum degree will be <=5

therefore option (d) will be the answer
0 votes
0 votes

Option D

e<=3n-6 ...(given)

We know that; $\delta$n<=2e;

Thus;

$\delta$n<=6n-12;

Try to satisfy this equation. If you put $\delta$ <=5; it will satisfy; but with $\delta$=6; 6n<=6n-12; which is wrong(although asymtotically its true but not mathematically).

Hence  6.

Answer:

Related questions

60 votes
60 votes
9 answers
1
Kathleen asked Sep 16, 2014
44,968 views
How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$
65 votes
65 votes
5 answers
2