GATE CSE
First time here? Checkout the FAQ!
x
0 votes
55 views

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?

 

 

asked in Graph Theory by Active (2k points)   | 55 views

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

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

1 Answer

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?

answered by Boss (6.7k points)  

Related questions

0 votes
1 answer
1
asked in Computer Networks by LavTheRawkstar Boss (5.8k points)   | 119 views
0 votes
0 answers
2
asked in Mathematical Logic by iita Active (1.9k points)   | 34 views
0 votes
1 answer
3
asked in Theory of Computation by Surya Dhanraj Active (1.2k points)   | 30 views


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3124 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,970 questions
32,072 answers
74,567 comments
30,150 users