recategorized by
21,015 views
33 votes
33 votes

The minimum number of edges in a connected cyclic graph on $n$ vertices is:

  1. $n-1$
  2. $n$
  3. $n+1$
  4. None of the above
recategorized by

5 Answers

Best answer
38 votes
38 votes
For making a cyclic graph, the minimum number of edges has to be equal to the number of vertices.
edited by
11 votes
11 votes

answer we be "n" because if you add a single edge also in spanning tree it will make a cycle .

spanning tree needs n-1 edges, so to make cycle it must have "(n-1)+1 edges . so option B is correct 

0 votes
0 votes

Its mentioned connected cyclic graph. Hence the minimum degree has to be 2.

Also minimum degree <= 2(no. of edges) / (no of vertices)

2 <= 2E V

hence option B is the answer  

Answer:

Related questions

39 votes
39 votes
8 answers
1
Kathleen asked Sep 15, 2014
17,642 views
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
19 votes
19 votes
3 answers
2
Kathleen asked Oct 8, 2014
5,677 views
Prove that in finite graph, the number of vertices of odd degree is always even.
39 votes
39 votes
4 answers
3
Kathleen asked Oct 8, 2014
13,037 views
Which scheduling policy is most suitable for a time shared operating system?Shortest Job FirstRound RobinFirst Come First ServeElevator
15 votes
15 votes
3 answers
4
Kathleen asked Oct 8, 2014
4,563 views
What are $x$ and $y$ in the following macro definition?macro Add x, y Load y Mul x Store y end macroVariablesIdentifiersActual parametersFormal parameters