Which of the following are true? In a graph G with ‘n’ vertices and ‘e’…
2023
Which of the following are true?
In a graph G with ‘n’ vertices and ‘e’ edges, sum of degrees of vertices = 2*e.
Eccentricity of a connected graph can never be equal to radius of the graph
Girth of a graph is the shortest cycle of the graph
Graph with equal degree for all vertices is multigraph
Answer: D. None of the above — 1. Sum of degrees = 2e: This is the Handshaking Lemma, which states that in any graph, the sum of vertex degrees equals twice the number of edges. (True) 2.…
- A.
(i), (ii), (iii)
- B.
(ii), (iii), (iv)
- C.
(i), (iii), (iv)
- D.
None of the above
Attempted by 14 students.
Show answer & explanation
Correct answer: D
1. Sum of degrees = 2e: This is the Handshaking Lemma, which states that in any graph, the sum of vertex degrees equals twice the number of edges. (True)
2. Eccentricity vs Radius: The radius of a graph is the minimum eccentricity among all vertices, not necessarily equal to the eccentricity of every vertex. (False)
3. Girth: The girth of a graph is defined as the length of its shortest cycle. (True)
4. Regular Graph: A graph with equal degree for all vertices is a regular graph, which can be simple or multigraph. (False)
Since statements 1 and 3 are true, but the available options do not match this combination, 'None of the above' is the correct selection.