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

@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 nothing but spanning tree

so (a) n-1

An acyclic graph may be a connected graph maybe a disconnected graph. An acyclic-connected graph is a tree and a collection of such trees is known as a forest.

An acyclic undirected graph is given in this question, So it can be a tree or a forest. But we want to maximize the number of edges(maximally connected) without making any cycle. So it must be a tree.

A tree with n vertices will have (n-1) edges.

NOTE:

If no of edges is greater than or equal to no of vertices in a graph then the graph must be cyclic.

### 1 comment

But we want to maximize the number of edges(maximally connected) without making any cycle. So it must be a tree.

i think the tree is always minimally connected  not maximally connected

see this ,  theorem no.6 → https://www.geeksforgeeks.org/some-theorems-on-trees/

5
9,650 views