Register

GO CLASSES DPP | Discrete Mathematics | Graph theory | UGC NET

• retagged by
596 views
3 3 votes

The minimum number of edges in a connected graph with ${ }^{\prime} n^{\prime}$ vertices is equal to

  1. $n(n-1)$
     
  2. $\frac{n(n-1)}{2}$
     
  3. $n^2$
     
  4. $n-1$

3 Answers

0 0 votes

The minimum number of edges for undirected connected graph is ( $\mathbf{n - 1}$ ) edges.
For the maximum number of edges (assuming simple graphs), every vertex is connected to all other vertices which gives arise for $n(n-1) / 2$ edges (use handshaking lemma).
 

 

• reshown by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO CLASSES DPP | Dis...Next → · Probability
← Previous in category · GO CLASSES DPP | Dis...Next in category → · NIELIT Scientific As...
Position:
Show:

Related questions

2 2 votes
2 2 answers
472
472 views
GO Classes asked Jul 23, 2025
472 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | UGC NET
The number of edges in a complete graph of $n$ vertices is$n$ $n(n-1) / 2$ $n(n+1) / 2$ $\left(n^{\wedge} 2\right) / 2$
1 1 vote
2 2 answers
372
372 views
GO Classes asked Jul 23, 2025
372 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | UGC NET
An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices areAll of even degreeAll of odd degreeOf any degreeEven in number
2 2 votes
4 4 answers
471
471 views
GO Classes asked Jul 23, 2025
471 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | TIFR
A graph is $d$ - regular if every vertex has degree $d$. For a $d$ - regular graph on $n$ vertices, which of the following must be TRUE?$d$ divides $n$At least one of $d$...
2 2 votes
3 3 answers
455
455 views
GO Classes asked Jul 23, 2025
455 views
GO CLASSES DPP | Discrete Mathematics | Graph theory | TIFR
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no st...