edited by
6,914 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$
edited by

8 Answers

Best answer
34 votes
34 votes

This is possible with spanning tree. 

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

Therefore, Answer is (A)

edited by
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.
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

34 votes
34 votes
2 answers
1
Ishrat Jahan asked Nov 2, 2014
12,922 views
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?$10$$11$...
57 votes
57 votes
3 answers
2
37 votes
37 votes
7 answers
3
Ishrat Jahan asked Oct 31, 2014
8,718 views
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...
73 votes
73 votes
6 answers
4
Ishrat Jahan asked Oct 29, 2014
21,328 views
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ?$1$$2$$3$$n$