edited by
3,456 views
4 votes
4 votes

Consider the following statements:

  1. A graph in which there is a unique path between every pair of vertices is a tree.
  2. A connected graph with e=v-1 is a tree
  3. A connected graph with e=v-1 that has no circuit is a tree

Which one of the above statements is/are true?

  1. I and III
  2. II and III
  3. I and II
  4. All of the above
edited by

1 Answer

Best answer
4 votes
4 votes

Lets go one by one,

(i) A graph in which there is a unique path between every pair of vertices is a tree.

==> This statement is true, Because graph can have unique path only when it does not have cycle. And according to the definition of tree, its a graph without cycel. Hence this is a valid statement.

(ii) A connected graph with e = v − 1 is a tree.

==> This statement is true. Not every graph with e = v - 1, will be a tree. But if the graph is connected hence its true. 

(iii) A graph with e = v − 1 that has no circuit is a tree.

==> This statement is also true, Here he has not mentioned the connected thing, but mentioned that it has no circuit. It means that its connected.

You can also proof these, just by taking some example. For the formal Proof check this

selected by
Answer:

Related questions

3 votes
3 votes
1 answer
1
go_editor asked Jul 20, 2016
10,291 views
A simple graph G with n vertices is connected if the graph has(n-1)(n-2)/2 edgesmore than (n-1) (n-2)/2 edgesless than (n-1) (n-2)/2 edges$\Sigma_{i=1}^k C(n_i, 2)$ edges...
4 votes
4 votes
3 answers
2
go_editor asked Jul 20, 2016
10,562 views
Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is2451495048519900
1 votes
1 votes
2 answers
4
go_editor asked Jul 20, 2016
4,482 views
The efficient data structure to insert/delete a number in a stored set of number isQueueLinked listDoubly linked listBinary tree