retagged by
2,084 views
18 votes
18 votes

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

1 Answer

Best answer
31 votes
31 votes

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

  • You need at least $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 options 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.

edited by
Answer:

Related questions