The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+29 votes

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

  1. $3$
  2. $4$
  3. $5$
  4. $6$
asked in Graph Theory by Veteran (59.6k points)
edited by | 2.3k views
What about k33 it is also fails the face contain cycle of three ? Answer should be A.

6 Answers

+37 votes
Best answer

Say every vertex has a minimum degree, therefore, least number of edges that will be in the graph is given by the handshaking lemma as $\frac{min \times |v|}{2}$

But the maximum number of edges for such a graph is defined in the question as $3\times |v| - 6$

Putting the minimum number of edges obtained by handshaking lemma in the given inequality, we get:

$\frac{min \times |v|}{2} \leq 3\times |v| - 6$

$\quad \frac{6 \times |v|}{2} \leq 3\times |v| - 6\text{; putting min degree as 6}$

$\;3 \times |v| \leq 3\times |v| - 6$

$\qquad\;\;0 \leq - 6 $

which is definitely inconsistent.

Hence, answer = option (D)

answered by Boss (30.8k points)
edited by
+23 votes

Let the min-degree of $G$ be $x$. Then $G$ has at least $\left[|v|\times \frac{x}{2}\right]$ edges.

$\left[|v|\times \frac{x}{2}\right]\leq \left[\left(3\times |v|\right) -6\right]$

for $x=6$, we get $0 \leq {-6}$, Therefore, min degree of $G$ cannot be $6$.

Correct answer is (D).

$\text{An alternative approach,}$

Let the min_degree of a graph be $\text{'x'}$ , then

 $x\leq \left(\frac{2e}{n}\right)$,
given  , $e\leq \left(3n - 6\right)$          $\text{\{it will be planner graph\}}$
put the value of $e$ ,then min_degree will be ,

 $x\leq \frac{(2(3n-6))}{n}$
 $x\leq \frac{\left(6n - 12\right)}{n}$
 $x\leq \left( \frac{6n}{n} - \frac{12}{n} \right)$
 $x\leq \left(6 - \frac{12}{n}\right)$ ,
 when number of vertices is more , then value of

$\left(\frac{12}{n}\right)$ will be less , $\left(\frac{12}{n} = 0.000001 \text{assume}\right)$ ,

then min_degree will be ,

$x\leq \left(6 - 0.000001\right)$
$x\leq 5.999999$  , max value
$x\leq \text{floor value}\left(5.9999999\ldots \right)$
$x = 5$ , maximum value of min_degree of defined graph (i.e. planner graph)

answered by Loyal (5.7k points)
edited by
ans is D or C??
If we put x=4 then


-1<= -6 becomes false

Plz explain.
@ diksha,

if you put x=4 then equation becomes -|V| <= -6 not -1 <= -6.
+15 votes

Given that, |E| ≤3 |V| − 6

We know that the inequality, min-degree ≤ 2|E| / |V| .

Put the value of |E| into inequality.

min-degree ≤ 6 - 12 / |V|

let min-degree is m.

m ≤ 6 - 12 / |V|

So our eqn will become , |V| ≥ 12 / (6-m) .

Apply hit and try to check all the options.

Option (a) 3   ,put m=3 then  |V| ≥ 4 .Yes, it is possible.

Option (b) 4 ,put m=4 then  |V| ≥ 6 .Yes ,it is possible.

Option (c) 5  ,put m=5 then  |V| ≥ 12 .Yes, it is possible.

Option (d) 6   ,put m=6 then  |V| ≥ 12/0 . It is NOT possible due to Divide by Zero or indeterminant state.

Therefore, min-degree of G cannot be 6.

The correct answer is (D) 6

answered by Loyal (6.8k points)

No need to use hit and trial.

m ≤ 6 - 12 / |V|   , Now since |V| is a positive number, 12/|V| will be positive as well hence,  6- 12/|V| will be less than 6 [since we are deducting some positive number from 6 so, result will be definitely less than 6]

So, m ≤ (something less than 6)  implies----> m<6  

+2 votes
Summation of degree = 2* no. of edges

                                   = 2( 3V -6)

Let min degree be d, then

d*V<= 2*(3V-6)


Taking V on left side-

(d-6)*V<= -12

Multiplying both side by (-1)

(6-d)*V>= 12

Minimum value of d should be 6 to make left side positive as no. of Vertices can't be negative.

Thus minimum degree, d=6.
answered by Active (1.8k points)
+1 vote

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.

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


suppose degree of all vertices is 6 then,


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

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

answered by Active (4.2k points)
+1 vote
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
answered by Active (4.9k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,870 questions
47,531 answers
62,297 users