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

10 Comments

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.
0
0
no cycle means tree....with n vertices...n-1 edges
0
0
Tree is maximally acyclic.
0
0

@ 

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

 

2
2
We have to make it a connected graph for maximum number of edges.
2
2
  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?
0
0

 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.

1
1
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