GATE CSE 1995 | Question: 1.25

Question

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

• A. $n-1$
• B. $n$
• C. $n+1$
• D. None of the above

Comments

But if  when the number of vertices given is 2 then the number of edges will be ???

---

@priyankapatel

For a Cycle Graph,

No of vertices $\geqslant$ 3 

---

Nice

Answer 1

For making a cyclic graph, the minimum number of edges has to be equal to the number of vertices.

Comments

for any cycle graph $C_n$ the number of edges =$n$

---

every cyclic graph is not a cycle graph

Answer 2

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 

Answer 3

Ans: B

eg. triangle, square etc.

Answer 4

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