The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 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.
asked in Graph Theory by Boss (40.5k points)
edited by | 454 views

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

Example for Option E) 

nice explanation @pragy sir

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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,071 questions
49,594 answers
65,786 users