ISRO 2024

Question

Which of the following are true​​​​​​?

1. In a graph G with ‘n’ vertices and ‘e’ edges, sum of degrees of vertices = 2*e.
2. Eccentricity of a connected graph can never be equal to radius of the graph
3. Girth of a graph is the shortest cycle of the graph
4. Graph with equal degree for all vertices is multigraph

1. (i), (ii), (iii)
2. (ii), (iii), (iv)
3. (i), (iii), (iv)
4. None of the above

Comments

1st and 3rd is true only other are false so answer is d

Answer 1

The correct statement is:

(ii), (iii), (iv)

Explanation:

• (i) is false. The sum of the degrees of vertices in an undirected graph is always twice the number of edges, i.e., ∑degrees=2e.

• (ii) is true. In a connected graph, the eccentricity (maximum distance from a vertex to any other vertex) can never be equal to the radius (minimum eccentricity among all vertices). This is because the radius is the minimum eccentricity, so it must be smaller.

• (iii) is true. The girth of a graph is the length of the shortest cycle in the graph.

• (iv) is true. A graph with equal degree for all vertices is called a regular graph, and if it allows multiple edges between the same vertices, it becomes a multigraph.

Comments

consider a cycle graph which has equal degree for all the vertices but that is a simple graph not multi graph

Answer 2

option A should be correct. IV statement is wrong. Graph with equal degree for all vertices is Regular Graph.