The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
268 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 in Graph Theory by Veteran (42.9k points)
edited by | 268 views

any acyclic connected graph is a tree.

1 Answer

+14 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 Veteran (20k points)

Example for Option E) 



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

29,167 questions
36,992 answers
92,225 comments
34,837 users