ISRO CSE 2009 | Question: 55

Question

In a graph $\text{G}$ there is one and only one path between every pair of vertices then $\text{G}$ is a

• A. Path
• B. Walk
• C. Tree
• D. Circuit

Comments

A Graph G(V,E) called as TREE if there is exactly one path between every two vertices.

Answer 1

Let G be a graph and let there be exactly one path between every pair of vertices in G. So G is connected. Now G has no cycles, because if G contains a cycle, say between vertices u and v, then there are two distinct paths between u and v, which is a contradiction.
Thus G is connected and is without cycles, therefore it is a tree.

Comments

@ ManojK can u please specify the diagram for understanding. I’m getting a complete graph...thanks in advance

Answer 2

ans is (c)

 path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another. In a directed graph, a directed path (sometimes called dipath^[1]) is again a sequence of edges (or arcs) which connect a sequence of vertices, but with the added restriction that the edges all be directed in the same direction.

walk is any route through a graph from vertex to vertex along edges. A walk can end on the same vertex on which it began or on a different vertex. A walk can travel over any edge and any vertex any number of times.

a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree

A circuit is path that begins and ends at the same vertex. Cycle. A circuit that doesn't repeat vertices is called a cycle. A Connected Graph. A graph is said to be connected if any two of its vertices are joined by a path

Comments

@kvkumar.

In a walk, no edge is traversed more than once. But vertex may appear mor than once. So cycle can b part of the walk.

A path is an open walk where no vertex is repeated more than once.

So, why not (A) the answer? And isnt tree a path ?

Answer 3

Ans C) Tree