in Graph Theory edited by
5,382 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

0 votes
0 votes
This is nothing but spanning tree

so (a) n-1
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

1 comment

But we want to maximize the number of edges(maximally connected) without making any cycle. So it must be a tree.

i think the tree is always minimally connected  not maximally connected

see this ,  theorem no.6 → https://www.geeksforgeeks.org/some-theorems-on-trees/

0
0
Answer:

Related questions