in Graph Theory edited by
5,397 views
25 votes
25 votes

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$
in Graph Theory edited by
5.4k views

4 Comments

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

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

@, thank you, understood!

0
0

6 Answers

34 votes
34 votes
Best answer

This is possible with spanning tree. 

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

Therefore, Answer is (A)

edited by

4 Comments

Note : undirected & acyclic
0
0
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.
0
0
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
1
1

This is possible with spanning tree

 

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

Related questions