Euler and Hamiltonian Graph MCQs: 12 Solved Questions with Explanations

Solve 12 Euler and Hamiltonian graph MCQs with concise explanations of parity tests, spanning cycles, complete graphs, route checks, and sufficient conditions.

KnowledgeGate Team

Exam prep & CS education

Updated 20 Sep 20267 min read

Euler questions track edges; Hamiltonian questions track vertices, and the exam trap is deciding whether a degree condition is necessary, sufficient, both, or neither. Parity, connectivity, route obstructions, complete and bipartite graph structure, cycle counts, Dirac's theorem, and Ore's theorem each require a different test. The earlier Graph Theory MCQs mixes three of these questions with colouring, planarity, and trees. Q3, Q4, and Q9 recur here so the second pass can focus on parity, connectivity, and cycle-count logic; review Graph Theory for GATE CS first if the definitions need refreshing.

1. Euler Circuit Definitions and the Even-Degree Test

An Euler circuit is a closed trail using every edge exactly once; it may repeat vertices. A Hamiltonian circuit visits every vertex once before returning to its start.

Q1. UGC NET Computer Science, December 2010

An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are: (a) all of even degree (b) all of odd degree (c) of any degree (d) even in number

(a) (a) only
(b) (b) and (c)
(c) (c) only
(d) (d) only

Answer: (a) (a) only. Connectivity and all-even degrees are required. Trail edges pair into entry and exit at every vertex, including the start. See the full solution.

Q2. ISRO Computer Science, 2016

A given connected graph is a Euler Graph if and only if all vertices of are of

(a) same degree
(b) even degree
(c) odd degree
(d) different degree

Answer: (b) even degree. Degrees need not be equal: a connected graph with degrees 2, 2, 2, 4, 4 passes because all are even. See the full solution.

2. Apply Degree Parity to a Construction and a Graph Family

Q3. GATE Computer Science, Information Technology, 2008

G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be

(a) regular
(b) Complete
(c) Hamiltonian
(d) Euler

Answer: (d) Euler. By the handshaking lemma, the odd-degree vertex count is even. Each gains one, while deg(v) is even. This conclusion uses the usual exam assumption that G is connected. Without that assumption, a separate all-even component would still require a connectivity check. See the full solution.

Q4. GATE Computer Science, 2007

Which of the following graphs has an Eulerian circuit?

(a) The complement of a cycle on 25 vertices
(b) A complete graph on 90 vertices
(c) Any k-regular graph where k is an even number
(d) None of the above

Answer: (a) The complement of a cycle on 25 vertices. Each complement degree is 25 - 1 - 2 = 22, and the complement is connected. Every K_90 degree is 89; even-regular graphs may be disconnected, as two disjoint cycles show. See the full solution.

3. Read the Figure Before Naming the Graph

Q5. UGC NET Computer Science, August 2016

Given the following graphs :

Graphs G1 and G2 with vertices a to e from the Euler-circuit question.

Which of the following is correct ?

(a) G 1 contains Euler circuit and G 2 does not contain Euler circuit.
(b) G 1 does not contain Euler circuit and G 2 contains Euler circuit.
(c) Both G 1 and G 2 do not contain Euler circuit.
(d) Both G 1 and G 2 contain Euler circuit.

Answer: (c) Both G 1 and G 2 do not contain Euler circuit. In G1, a, b, c, e have degree 3, while d has degree 2; four odd vertices rule out an Euler circuit. In G2, a and d are odd. See the full solution.

Q6. UGC NET Computer Science, December 2014

Consider the Graph shown below :

Six-vertex graph with corners A, B, C, D and interior points E and F from the graph-type question.

This graph is a __________.

(a) Complete Graph
(b) Bipartite Graph
(c) Hamiltonian Graph
(d) All of the above

Answer: (c) Hamiltonian Graph. The cycle A-B-C-E-F-D-A visits all six vertices once. Missing edges make the graph incomplete, and the triangle B-C-E makes it non-bipartite, so option (d), All of the above, fails. See the full solution.

G1 and G2 each have odd-degree vertices, so neither has an Euler circuit; the six-vertex graph traces the Hamiltonian cycle A-B-C-E-F-D-A.

4. Hamiltonian Routes and Complete Bipartite Graphs

Q7. GATE Computer Science, Set 2, 2026

Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways. A salesperson needs to make a trip. She needs to: Start from a city; Visit each remaining city exactly once; Return to the starting city. Which one of the following options is true?

Two intercity highway maps: a grid of cities and a five-city network, from the salesperson-route question.

(a) Such a trip is possible for (i), but not for (ii).
(b) Such a trip is possible for (ii), but not for (i).
(c) Such a trip is possible for both (i) and (ii).
(d) Such a trip is possible neither for (i) nor for (ii).

Answer: (a) Such a trip is possible for (i), but not for (ii). One grid cycle is r1c1-r1c2-r1c3-r1c4-r2c4-r2c3-r2c2-r3c2-r3c3-r3c4-r4c4-r4c3-r4c2-r4c1-r3c1-r2c1-r1c1. In (ii), degree-2 vertices v, x, y force three edges at u, but a cycle uses two. See the full solution.

Q8. UGC NET Computer Science, June 2019

For which values of m and n does the complete bipartite graph K_m,n have a Hamiltonian circuit?

(a) m != n, m,n >= 2
(b) m != n, m,n >= 3
(c) m = n, m,n >= 2
(d) m = n, m,n >= 3

Answer: (c) m = n, m,n >= 2. Bipartite cycles alternate between parts, so a Hamiltonian circuit needs equal sizes. The cycle u1-v1-u2-v2-u1 in K_2,2 proves the lower bound is 2. See the full solution.

The 4x4 grid traces a 16-vertex Hamiltonian cycle, while the five-city graph forces three edges at one vertex, so no cycle exists.

5. Count Hamiltonian Cycles and Recognise a Sufficient Condition

Q9. GATE Computer Science, 2019

Let 𝐺 be an undirected complete graph on 𝑛 vertices, where 𝑛 > 2. Then, the number of different Hamiltonian cycles in 𝐺 is equal to

(a) 𝑛!
(b) (𝑛 − 1)!
(c) 1
(d) (n - 1)! / 2

Answer: (d) (n - 1)! / 2. Fixing one start removes rotations, leaving (n-1)! orders; divide by 2 because reversals match. For n=5, (5-1)!/2 = 4!/2 = 24/2 = 12. See the full solution.

Q10. UGC NET Computer Science, December 2018

If a simple graph G has n >= 3 vertices, then G is Hamiltonian if:
(i) deg(v) >= n/3 for every vertex v
(ii) deg(v) + deg(w) >= n whenever v and w are not adjacent
(iii) E(G) >= (n - 1)(n - 2)/3 + 2
Choose the correct answer from the code given below.

(a) (i) and (iii) only
(b) (ii) only
(c) (ii) and (iii) only
(d) (iii) only

Answer: (b) (ii) only. Statement (ii) is Ore's sufficient condition for a simple graph with n >= 3. Statement (i) fails for two disjoint K3 graphs at n = 6: every degree is 2 = n/3, but the graph is disconnected. Statement (iii) fails for K5 plus an isolated vertex: at n = 6 it has 10 edges, above the threshold 26/3, but no Hamiltonian cycle. See the full solution.

6. Use Dirac's Bound, Then Separate True and False Statements

Q11. UGC NET Computer Science, August 2024

A graph G with number of vertices greater and equal than three i.e. (n≥3) is a Hamiltonian graph, if the degree of each vertex is greater and equal to ....

(a) Equal to number of vertices
(b) Double of number of vertices
(c) Half of number of vertices
(d) Four times of number of vertices.

Answer: (c) Half of number of vertices. Dirac's sufficient condition is deg(v) >= n/2 for every vertex in a simple graph when n >= 3. For n=8, 8/2 = 4 suffices but is not necessary. See the full solution.

Q12. UGC NET Computer Science, December 2015

Which of the following statements are false?
(a) A connected multigraph has an Euler circuit if and only if every vertex has even degree.
(b) A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two odd-degree vertices.
(c) A complete graph K_n has a Hamiltonian circuit whenever n >= 3.
(d) A cycle C6 is not bipartite, but a complete graph K3 is bipartite.
Codes:

(a) (a) only
(b) (b) and (c)
(c) (c) only
(d) (d) only

Answer: (d) (d) only. Statements (a) and (b) are the two Euler tests, and (c) holds for K_n when n >= 3. Statement (d) reverses both facts: C6 is bipartite by alternating vertices, while K3 has a 3-cycle and is not bipartite. See the full solution.

7. What These Questions Test and What to Practise Next

The key ideas are Euler parity and connectivity, Hamiltonian routes and obstructions, cycle counting, and Dirac's and Ore's sufficient conditions. Keep this checklist:

Euler circuit -> connected + every degree even
Euler path only -> exactly two odd degrees
Hamiltonian -> find a spanning cycle or a structural obstruction
K_m,n -> equal parts for a Hamiltonian circuit
K_n undirected cycles -> (n-1)!/2

After a timed attempt, use the GATE CS exam preparation page to choose the next graph-theory topic. First, redraw Q5's degree table and Q7's 4 x 4 route from memory, then explain every rejected option.

For structured study, use GATE Guidance by Sanchit Sir. To strengthen the mathematical base, try Engineering Mathematics for GATE. Choose the route matching your gap, then solve these 12 questions again without the explanations.

Keep learning

Graph Traversal MCQs: 12 Solved Questions on Walks, Paths, Trails, Circuits and Connectivity

Attempt 12 graph traversal and connectivity questions, then check each answer through definitions, reachability, degree conditions and edge-count arguments.

Updated 3 Oct 20267 min readDiscrete Mathematics MCQs