Solved Paper-II On Topic : Solved Paper-II December 2005

Que : 1 . T is a graph with n vertices. T is connected and has exactly n-1 edges, then:

1. T is a tree
2. T contains no cycles
3. Every pairs of vertices in T is connected by exactly one path
4. All of these
Please Select Ans Options .

Option 4 is Correct Answer
Acyclic graph is called Tree, It means which connect the all vertices by exactly once.
Theorem : The following are equivalent in a graph T with n vertices.
a) T is connected and contains no cycles.
b) T is connected and has n-1 edges.
c) T has n-1 edges and contains no cycles.
d) T is connected and each edge is a bridge.
e) Any two vertices of T are connected by exactly one path.
f) T contains no cycles, but the addition of any new edge creates exactly one cycles.