Which of the following statements is FALSE?

Question

Question

This question was previously asked in

Beltron Programmer 1 Oct 2023 Official Paper

Attempt Online

Not all graphs with an Eulerian cycle have a Hamiltonian cycle.
The maximum degree of a vertex in a graph can be d, where d is the number of vertices in the graph.
The maximum number of edges on a graph G with n vertices with no cycle is n - 1.
If G is a graph of 7 vertices such that the sum of the vertices' degrees is at least 21, then there is a vertex with 4 neighbors.

Answer 1

The correct answer is Option 2) The maximum degree of a vertex in a graph can be d, where d is the number of vertices in the graph.

Key Points

This statement is false because in a simple undirected graph (no self-loops), the maximum degree of a vertex is n - 1, where n is the number of vertices.
A vertex cannot be connected to itself, so it can be connected to at most all other n - 1 vertices.

Additional Information

Option 1 - True: Not all graphs with an Eulerian cycle (visiting each edge exactly once) necessarily have a Hamiltonian cycle (visiting each vertex exactly once). These are two distinct properties.
Option 3 - True: A graph with n vertices and no cycles is a tree or forest, and such a graph has at most n - 1 edges.
Option 4 - True: If the sum of degrees is at least 21 in a 7-vertex graph, then by the Pigeonhole Principle, at least one vertex must have degree ≥ 4 (since 21/7 = 3 and degrees are integers).