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$

### 4 Comments

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!

## 6 Answers

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.

So the answer is A.

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/

Answer:

33 votes
2 answers
5
9,650 views
55 votes
3 answers
6
8,277 views
36 votes
7 answers
7
6,555 views
67 votes
6 answers
8
15,188 views