Dark Mode

65 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)**

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

4

0

38 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)

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

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

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