Register

ISRO2009-55

• edited by
5,404 views
7 votes
7 votes

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

  1. Path
  2. Walk
  3. Tree
  4. Circuit
• edited by
User Avatar

3 Answers

Best answer
10 votes
10 votes

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.

• selected by
User Avatar
3 votes
3 votes

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

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

8 votes
8 votes
3 answers
1
go_editor asked Jun 15, 2016
3,436 views
ISRO2009-56
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most $n$ edges $n-k$ edges $(n-k) (n-k+1)$ edges $(n-k) (n-k+1)/2$ edges
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most$n$ edges$n-k$ edges$(n-k) (n-k+1)$ edges$(n-k) (n-k+1)/2$ e...
User Avatar
9 votes
9 votes
1 answer
2
go_editor asked Jun 15, 2016
8,975 views
ISRO2009-54
A graph in which all nodes are of equal degree, is known as Multigraph Non regular graph Regular graph Complete graph
A graph in which all nodes are of equal degree, is known asMultigraphNon regular graphRegular graphComplete graph
User Avatar
65 votes
65 votes
5 answers
3
Kathleen asked Sep 16, 2014
15,377 views
GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must neces...
User Avatar
8 votes
8 votes
1 answer
4
go_editor asked Jun 15, 2016
2,868 views
ISRO2009-52
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is $e$ $e/2$ $e^2$ $2 e$
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is$e$$e/2$$e^2$$2 e$
User Avatar
Link Copied!