Register

GATE IT 2004 | Question: 5

• edited by
7,054 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
User Avatar

8 Answers

0 votes
0 votes

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.

Ref: Tree (graph theory) - Wikipedia

User Avatar
0 votes
0 votes

The minimum no of edges needed to minimally connect any graph is n-1.Such a graph is called a tree.A tree is 

i)Acyclic and connected → n-1 edges

ii)n-1 edges and connected → acyclic

iii)n-1 edges and acyclic → connected 

 

Now addition of 1 more edge will render the graph cyclic 

Correct answer is option B.

User Avatar
0 votes
0 votes

Acyclic graph are graph which doesnt contain cycle

 

here you can see using n vertices , it has maximum n-1 edges.

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

34 votes
34 votes
2 answers
1
Ishrat Jahan asked Nov 2, 2014
13,021 views
GATE IT 2004 | Question: 37
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$ $18$ $19$
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$...
User Avatar
57 votes
57 votes
3 answers
2
Ishrat Jahan asked Nov 3, 2014
10,583 views
GATE IT 2005 | Question: 56
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i...
User Avatar
37 votes
37 votes
7 answers
3
Ishrat Jahan asked Oct 31, 2014
8,880 views
GATE IT 2006 | Question: 11
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 a Hamiltonian cycle grid hypercube tree
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...
User Avatar
73 votes
73 votes
6 answers
4
Ishrat Jahan asked Oct 29, 2014
21,568 views
GATE IT 2007 | Question: 25
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$
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$
User Avatar
Link Copied!