in Graph Theory
551 views
0 votes
0 votes

every vertex has a minimum degree, therefore, least number of edges that will be in the graph is given by the handshaking lemma as = min×|v|/2=2 E is right?

in Graph Theory
by
551 views

1 comment

$\delta \leqslant \frac{2e}{v}\leq \Delta$.

Here $\delta$ is minimum degree and $\Delta$ is maximum degree.

1
1

1 Answer

0 votes
0 votes

Minimum degree of an vertex is 0 so there is possibility of 0 edges.

If you are asking minimum number of edge in an connected graph then.

Least number of edges such that graph can be connected is simply n-1

Least number of edges to ensure that graph must be connected is $\frac{(n-1)(n-2)}{2}$+1 or n-1C2+1

Given equation in question seems to be ambiguous because there is no proper definition of min  what is min referred as?

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