GATE IT 2004 | Question: 5

Question

What is the maximum number of edges in an acyclic undirected graph with $n$ vertices?

• A. $n-1$
• B. $n$
• C. $n+1$
• D. $2n-1$

Comments

@Yashdeep2000 that mean the graph is acyclic and adding one more edge between any two non adjacent vertices makes it cyclic . 

Moreover a tree is maximally acyclic graph.

---

@Kabir5454, thank you, understood!

---

 

The minimum no of edges needed to minimally connect any graph is n-1.Such a graph is called a tree.A tree is 

i)Acyclic and connected → n-1 edges

ii)n-1 edges and connected → acyclic

iii)n-1 edges and acyclic → connected 

 

Now addition of 1 more edge will render the graph cyclic 

Correct answer is option B.

Answer 1

This is possible with spanning tree. 

A spanning tree with $n$ nodes has $n-1$ edges.

Therefore, Answer is (A)

Comments

Note : undirected & acyclic

---

Can we consider the example of a star graph here? It has one node at the center, and $n-1$ nodes which are connected by $n-1$ edges. Hence, maximum number of edges will be $n-1$? Please correct me, if i’m wrong.

---

Yes u can say that..since adding even one more edge will create a cycle ..hence ur star graph example will have maximum n-1 edges

---

This is possible with spanning tree

 

Answer 2

Option A)  max no of edge in a connected graph is n-1, which doesn't form any cycle

Answer 3

Ans: n-1 e.g tree

if no of edge is greater than or equal to no of vertices then there must be a cycle.

Comments

Yes, or we can say atleast one cycle.

Answer 4

Any acyclic graph is a forest(collection of trees(collection of different connected components and each component is itself a tree). Now, since they have asked "maximum number of edges" ,there must be only one tree in the forest( single connected component) and we know a tree with n vertices has n-1 edges, hence answer is A.