UGC NET CSE | June 2009 | Part 2 | Question: 23

Question

Which two of the following are equivalent for an undirected graph  G ?

(i) G is a tree

(ii) There is at least one path between any two distinct vertices of G

(iii) G contains no cycles and has (n-1) edges

(iv) G has n edges

• A. (i) and (ii)     
• B. (i) and (iii)    
• C. (i) and (iv)   
• D. (ii) and (iii)

Answer 1

A connected acyclic graph is called a tree. Tree is connected (there is a path between any two distinct vertices) and has n-1 edges because of zero cycles and connectedness.

Answer B

Comments

@ Shivam Chauhan 

but they said "undirected graph"....how you consider it as a acyclic graph  ?

---

They asked which two statements are equivalent to each other if G is undirected graph.

Suppose I take (i) statement as true then (iii) must also be true because tree has zero cycles (acyclic) and n-1 edges

Consider your answer (ii) statement to be true then it implies only G is connected not about the number of edges so (iv) may or may not be true

Answer 2

Default graph is simple, undirected graph..

For simple graph, it has no self loop and parallel edges

Ans: D

Answer 3

Answer is D;

   As default graph is a simple graph & it is undirected
and it has  no self loop and parallel edges