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

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.7k points)
edited by | 2.7k views
0
What about k33 it is also fails the face contain cycle of three ? Answer should be A.

6 Answers

+39 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.9k points)
edited by
0
$|E|\leq 3\left | v \right |-6$ is formula for planar graph

Now, we can draw planar graph with degree $3$

but cannot draw planar graph with degree $4$,$5$,$6$

So, all three option is correct

what is wrong in this approach?
+3

@srestha mam

The formula which you gave is necessary condition of planar graphs but not sufficient condition

means every planar graph is should satisfy the condition, but it doesn't mean which graph is satisfied this condition necessarily to be the planar graph.

The sufficient condition is

A graph is planar if and only if it does not contain a subdivision of K5 and K3,3 as a subgraph.

for more details http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

0
ok

but how option B) and C) satisfying $\left | E \right |\leq 3v-6$ condition?
0
mam, did you mean for this question or your question?
0
this question

Say every vertex has degree 5

So, no of vertices=6

then , no of edges $\binom{6}{2}=15$

$15\leq 18-6$ which is not correct

So, it also satisfying answer
0

mam, read the question carefully.

A graph G=(V,E) satisfies |E|≤3|V|−6.

it means, the graph already satisfies the condition ( Avoid the graphs which doesn't satisfy, means n should be grater than what you taken ) , then what is minimum degree ?

0
I am not getting

Can u draw such a graph?

See, in ans, they use formula for handshaking lemma

which is nothing but a complete graph

right?
+2

given that e ≤ 3 n - 6 ,

we know that e ≥ $\frac{min.deg\;\;  n}{2}$

===> $\frac{min.deg\;\;  n}{2}$ ≤ 3 n - 6 , ====> min.deg . n ≤ 6 n - 12

by keeping min.degree = 5 ===> 5 n ≤ 6 n - 12 ===> 12 ≤ 6 n - 5 n ===> n ≥ 12

take n ≥ 12, check the condition.

 

See, in ans, they use formula for handshaking lemma

which is nothing but a complete graph

hand shaking lemma says, 2 |E| = sum of deg of each vertex

2 | E | = k. | N |, let assume all vertices have same degrees = k

===> | E | = $\frac{k\;\; | N |}{2}$

if k is the minimum degree, then Edges may increase in the graph.

===> | E | ≥ $\frac{k\;\; | N |}{2}$

But Complete graph forcing that k should be equal to n-1.

0
ok, yes thanks :)

but there is no direct formula of this $e\geq \frac{min degree(n)}{2}$

but until we assume it, we cannot solve this question
0

but there is no direct formula of this

mam, what it means? i derived it also in my last comment.

0
$\frac{min (deg)}{2}$ is there any formula like this?

we came to this formula from $2\left | E \right |=$ summation of degree of all vertices

from this

right?

that is what I mean
0
the numerator is multiplication of minimum degree with n.
0

 is there any formula like this?

@srestha For this example we have to work with average.

We know $min value\leqslant average \leqslant max value$

Hence $min value \leqslant 2\left | E \right |/\left | V \right |$ (Average degree per vertex) 

When we solve this equation using given values, you will get the answer.

+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
0
ans is D or C??
0
If we put x=4 then

|v|*4/2<=3|v|-6

-1<= -6 becomes false

Plz explain.
0
@ diksha,

if you put x=4 then equation becomes -|V| <= -6 not -1 <= -6.
+16 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 (7.1k points)
0

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)

d*V<=6V-12

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.

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.

answered by Active (4.4k 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)
Answer:

Related questions



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

44,317 questions
49,814 answers
164,548 comments
65,866 users