+10 votes
454 views

Which of the following is NOT a sufficient and necessary condition for an undirected graph $G$ to be a tree?

1. $G$ is connected and has $n -1$ edges.
2. $G$ is acyclic and connected.
3. $G$ is acyclic and has $n - 1$ edges.
4. $G$ is acyclic, connected and has $n - 1$ edges.
5. $G$ has $n - 1$ edges.
asked
edited | 454 views
0

any acyclic connected graph is a tree.

## 1 Answer

+19 votes
Best answer

Option a $\iff$ Option b $\iff$ Option c $\iff$ Option d.

• You need atleast $n-1$ edges to have a connected graph. This leaves no edges to make any cycles. Thus, Option a $\implies G$ is acyclic.
• A connected graph with $n-1$ edges is acyclic, as shown above. Now, if we add any more edges to this graph, we will be connecting two vertices that are already connected. Thus, adding any more than edges to a connected graph will cause cycles. So, if a graph is acyclic and connected, it has exactly $(n-1)$ edges.
• You can't fit $(n-1)$ edges between $(n-1)$ vertices without causing cycles. Thus, if graph with $(n-1)$ edges is acyclic, it must connect $n$ vertices. Hence, an acyclic graph with $(n-1)$ edges is connected.

Thus, all options, a to d are equivalent.

Option b $\iff G$ is a tree.

• Any acyclic connected graph is a tree by definition.
• A graph $G$ is a tree if it is both acyclic and connected by definition.

Thus, all option a to d are both necessary and sufficient for an undirected graph $G$ to be a tree.

Option e $\mathrel{\rlap{\hskip .5em/}}\Longrightarrow G$ is a tree.

• Since $G$ is not constrained to be acyclic, we can create a cyclic graph with $(n-1)$ edges. This graph will be cyclic, and it won't be connected. And thus, it won't be a tree.

Hence, option E is the correct answer.

answered by Boss (21.1k points)
edited by
+10

Example for Option E)

0
nice explanation @pragy sir
0

A tree is a minimally connected graph is all the hint we need here.

Answer:

+9 votes
3 answers
2
+11 votes
2 answers
3
+4 votes
1 answer
4
+9 votes
2 answers
5
+8 votes
2 answers
6