5,388 views

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

1. $n-1$
2. $n$
3. $n+1$
4. $2n-1$

okay got it, can you please help me in understanding “what is maximally acyclic graphs ”!?

@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.

@, thank you, understood!

This is possible with spanning tree.

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

Therefore, Answer is (A)

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

Option A)  max no of edge in a connected graph is n-1, which doesn't form any cycle
by
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.

### 1 comment

Yes, or we can say atleast one cycle.
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.

1
9,706 views