11,404 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$

What about k33 it is also fails the face contain cycle of three ? Answer should be A.
By handshaking lemma :

let K be the min degree of vertices then  $k*\left | V \right | < = 2 * |E|$

putting $|E| <= 3 |V| -6$ we get

$|V| <= \frac{-12}{(k-6)}$

Hence putting option D ie 6 is not possible :)

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.

@Satbir sir

i correct myself I misinterpret the above statement

the correct statement is following:

"Every planar graph contains at least one vertex with degree at most 5."

Dear Sir

Thanks for this ans. I just wanted to know why are we assuming minimum degree of all the vertices to be same, can’t every vertex have diff min degrees.
Can someone please to me,  how other options are not satisfying the equation?

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)

by

ans is D or C??
If we put x=4 then

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

-1<= -6 becomes false

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

by

### 1 comment

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.

### 1 comment

If d is less than 6 then also left side is a positive no ??

1
14,299 views
2
11,588 views
3
13,767 views