The Gateway to Computer Science Excellence
+2 votes
Consider the graph with 11 vertices and 16 edges. The maximum value of minimum degree of the graph is __________________
in Graph Theory by Veteran (119k points) | 344 views

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

$\delta \leq 2$

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?

I just know one formula

Sum of degree of graph=2*Number of edge

that is what the formula applied here too

1 Answer

+4 votes
Best answer
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


d'<= 2*e/11

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

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
50,737 questions
57,388 answers
105,417 users