42. Which of the following are true?
(i) In a graph G with 'n' vertices and 'e' edges, sum of degrees of vertices = 2*e
(ii) Eccentricity of a connected graph can never be equal to radius of the graph
(iii) Girth of a graph is the total number of edges in the shortest cycle of the graph
(iv) Graph with equal degree for all vertices is multigraph
(i), (ii), (iii)
(ii), (iii), (iv)
(i), (iii), (iv)
None of the above
ANSWER
Only statements (i) and (iii) are true, and no option lists exactly these two, so the answer is (d) None of the above.
Official answer: DSource: ISRO's revised and final answer key of 16 February 2024
Statement (i): each edge adds 1 to the degree of each of its two end vertices, so (handshaking lemma). True.
Statement (ii): the radius is the minimum eccentricity over all vertices, so at least one vertex always has eccentricity equal to the radius. For example, in a cycle every vertex has the same eccentricity, which equals the radius. So the claim that eccentricity can never equal the radius is False.
Statement (iii): girth is the length of the shortest cycle, that is, the number of edges in it. True.
Statement (iv): a graph whose vertices all have the same degree is a regular graph. A simple graph such as is regular and has no parallel edges, so it is not a multigraph. False.
The true statements are exactly (i) and (iii).
Options (a), (b) and (c) each include (ii) or (iv), so none of them lists exactly (i) and (iii). The correct choice is (d), None of the above.
KEY IDEA
Handshaking lemma gives degree sum ; the radius is the smallest eccentricity, so some vertex always attains it; girth is the number of edges in the shortest cycle; equal degrees mean a regular graph, not a multigraph.
WATCH OUT FOR
Accepting (iv) because regular graphs sound special, or thinking eccentricity differs from the radius for every vertex. Also picking option (c) without noticing (iv) is false.
From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 4 ISRO Graph theory questions, with notes
