Discussion
Consider the following statements :
(i) A graph in which there is a unique path between every pair of vertices is a tree.
(ii) A connected graph with e = v - 1 is a tree.
(iii) A graph with e = v - 1 that has no circuit is a tree.
Which of the above statements is/are true ?
Answer: D
All three statements are true. A graph with a unique path between every pair of vertices is connected and has no cycle, which is the definition of a tree. A connected graph with e = v - 1 is a tree, because a connected graph needs at least v - 1 edges and has a cycle if it has more. A graph with e = v - 1 and no circuit is a forest with exactly one component, so it too is a tree.
Since all three hold, no option which leaves one out is acceptable. Option D is correct. This is the standard set of equivalent definitions of a tree, any of which can be used to prove that a graph is a tree.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development