3.3k views

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

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.

edited by
+1
$|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?
+4

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

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

0

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?
+3

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.

0

What if options are not given?

Then how to approach such problems @Shaik Masthan Sir?

+1
generally, if k is degree of each vertices, then we can conclude k.V = 2 |E|

if k is minimum degree, then edges may be increases

∴ k.V ≤ 2.|E| ===> $\frac{k.V}{2}$ ≤ |E|

given that |E| ≤ ( 3 V - 6 )

==> $\frac{k.V}{2}$ ≤ ( 3 V - 6 )

k . V ≤ 6V - 12

k ≤ 6 - $\frac{12}{V}$

k ≤ 5.9999999

k must be not grater than or equal to 6
0

if k is minimum degree, then edges must be increased

0
it's a typo !

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$.

$\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)

edited
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.

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

+1

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

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.

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.

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

1
2