5,397 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$

Extra Information:
Spanning tree is maximally acyclic and minimally connected. So on removing single edge, it will form a cycle and removing single edge will make it a disconnected graph.
no cycle means tree....with n vertices...n-1 edges
Tree is maximally acyclic.

I think there is a typo, So on adding a single edge, it will form a cycle.

We have to make it a connected graph for maximum number of edges.
1. Why aren’t we considering case where there is self loop? acyclic doesn’t implies no self loop in graph, does it?
2. And what does maximally acyclic means(there has been some discussion about it in comment section) not getting proper info in internet?

self-loop is the edge that connects to the vertex itself. the self-loop itself creates a cycle so it is not allowed in 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.

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,745 views