343 views
Consider the graph with 11 vertices and 16 edges. The maximum value of minimum degree of the graph is __________________
| 343 views
+1

minimum degree, $\delta \leq \frac{2e}{v}$

$\delta \leq 2$

0
I'm new to graph theory can you please explain "The maximum value of minimum degree of the graph"?

is it same as what will be the minimum degree out of all the vertex in that graph?
0

I just know one formula

Sum of degree of graph=2*Number of edge

that is what the formula applied here too

d1+d2+d3....d11=2*e where di= degree of vertex i

Let minimum degree be d'. Then d'<=di for all i.

Replacing all the degrees with d' we get,

d'+d"......+d'(11 times each for 1 of the 11 vertices) <= 2*e

11d'<=2*e

d'<= 2*e/11

e=16  so d'<=2.9 hence d'=2.
by Boss (23.5k points)
selected by