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

Dark Mode

5,287 views

24 votes

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

- $n-1$
- $n$
- $n+1$
- $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.

0

34 votes

Best answer

0

1

3 votes

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.