Logical-Reasoning
December 20, 2024NTA UGC NET Dec 2023 Paper-2
December 21, 2024CMI 2021
| Question 4 |
Consider the following statements about finite simple graphs G:
(i)If each vertex of a graph G has degree at least 2 then G contains a cycle as a subgraph.
(ii)If the number of edges of a graph G is at least as large as the number of its vertices, then G contains a cycle as a subgraph.
Which of the above two statements holds for all graphs?
(i)If each vertex of a graph G has degree at least 2 then G contains a cycle as a subgraph.
(ii)If the number of edges of a graph G is at least as large as the number of its vertices, then G contains a cycle as a subgraph.
Which of the above two statements holds for all graphs?
| (i) only | |
| (ii) only | |
| both (i) and (ii) | |
| neither of them |
Question 4 Explanation:
(i) Let P = ⟨v1, v2, . . . , vt⟩ be a maximal path in G. Since vt has degree at least 2 in G, there is an edge {vt, x} in G which is different from the edge incident on vt in the path P. Since P is a maximal path the vertex x must belong to P. So x = vi for some 1 ≤ i < (t − 1). The path ⟨vi, v(i+1), . . . , vt⟩ together with the
edge {vt, vi} forms a cycle in G.
(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with
(i) one fewer vertex, and
(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.
But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.
edge {vt, vi} forms a cycle in G.
(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with
(i) one fewer vertex, and
(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.
But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.
Correct Answer: C
Question 4 Explanation:
(i) Let P = ⟨v1, v2, . . . , vt⟩ be a maximal path in G. Since vt has degree at least 2 in G, there is an edge {vt, x} in G which is different from the edge incident on vt in the path P. Since P is a maximal path the vertex x must belong to P. So x = vi for some 1 ≤ i < (t − 1). The path ⟨vi, v(i+1), . . . , vt⟩ together with the
edge {vt, vi} forms a cycle in G.
(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with
(i) one fewer vertex, and
(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.
But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.
edge {vt, vi} forms a cycle in G.
(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with
(i) one fewer vertex, and
(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.
But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.