Euler and Hamiltonian Graphs: Definitions, Conditions and Worked Examples

Learn what must be used exactly once in Euler and Hamiltonian problems. Classify one graph both ways, test the key theorems, and avoid common traps.

KnowledgeGate Team

Exam prep & CS education

Updated 9 Nov 20266 min read
Euler and Hamiltonian Graphs: Definitions, Conditions and Worked Examples

Euler and Hamiltonian questions both ask for one continuous traversal. The key difference is what cannot repeat: an Euler problem controls edges, while a Hamiltonian problem controls vertices. Degree counting can settle the Euler question, but no matching shortcut characterises every Hamiltonian cycle. The same six-vertex graph has an open Euler trail and a Hamiltonian cycle, while two counterexamples show why the converse implications fail. The Graph Theory review is the compact cross-topic map for degrees, paths, planarity, colouring, connectivity and trees. Euler/Hamiltonian classification itself depends on route construction, theorem checks and counterexamples. Use this habit: name the object, test the conditions, then construct a route.

Euler versus Hamiltonian: identify what must appear once

A walk is a vertex sequence in which consecutive vertices are adjacent. It may repeat vertices and edges.

An Euler trail uses every edge exactly once and may revisit vertices. An Euler circuit is such a trail with the same start and end. A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to its start. Repeating that start vertex is allowed.

Object

Used exactly once

May leave edges unused?

Must return to start?

Fast condition

Euler trail

Every edge

No

No

Connected edge-bearing part and exactly 0 or 2 odd vertices

Euler circuit

Every edge

No

Yes

Connected edge-bearing part and 0 odd vertices

Hamiltonian path

Every vertex

Yes

No

No Euler-style degree-parity characterisation

Hamiltonian cycle

Every vertex except the repeated start

Yes

Yes

No Euler-style degree-parity characterisation

An Eulerian graph contains an Euler circuit, while a Hamiltonian graph contains a Hamiltonian cycle. An open Euler trail between two odd vertices is not an Euler circuit.

Euler conditions and the six-vertex worked example

Six-vertex graph G with degrees and an eight-edge Euler trail from A to E highlighted.

For a finite undirected graph, ignore isolated vertices. All edge-bearing vertices must lie in one connected component. Then:

  • zero odd-degree vertices gives an Euler circuit;

  • exactly two odd-degree vertices gives an open Euler trail, starting at one odd vertex and ending at the other;

  • more than two odd-degree vertices gives neither.

By the handshaking lemma, the degree sum equals twice the edge count, so the number of odd-degree vertices is always even.

Consider

V = {A, B, C, D, E, F}

and

E = {AB, BC, CD, DE, EF, FA, AC, CE}.

The degrees are

deg(A) = 3, deg(B) = 2, deg(C) = 4, deg(D) = 2, deg(E) = 3, deg(F) = 2.

Check the arithmetic against the eight edges:

3 + 2 + 4 + 2 + 3 + 2 = 16 = 2 x 8 = 2|E|.

Only A and E are odd, and G is connected. Therefore, G has an open Euler trail between A and E but no Euler circuit.

One witness is

A-B-C-D-E-F-A-C-E.

Its edge order is AB(1), BC(2), CD(3), DE(4), EF(5), FA(6), AC(7), CE(8). These are exactly the eight edges in E, each used once. The endpoints are the odd vertices A and E.

Graph G on vertices A to F, degrees A:3, B:2, C:4, D:2, E:3, F:2, with its eight edges numbered as an Euler trail from A to E.

For more parity practice, use Engineering Mathematics for GATE.

Test the same graph for a Hamiltonian path or cycle

Now switch from edges to vertices. The outer route A-B-C-D-E-F-A is a Hamiltonian cycle: every other vertex appears once before the return to A. Chords AC and CE may remain unused. Removing the final FA gives the Hamiltonian path A-B-C-D-E-F.

So G has an open Euler trail from A to E, no Euler circuit, and a Hamiltonian cycle.

Here n = 6, so Dirac's threshold is n/2 = 3. Although delta(G) = 2, the cycle proves G is Hamiltonian. Failing Dirac's condition does not prove non-Hamiltonicity.

Two counterexamples that break the false implications

First, let the complete bipartite graph K2,4 have parts X = {u, v} and Y = {1, 2, 3, 4}.

Every vertex in X is adjacent to every vertex in Y, and there are no edges inside a part.

Vertices u and v each have degree 4, while vertices 1, 2, 3 and 4 each have degree 2. The graph is connected and every degree is even, so it has an Euler circuit. One witness is u-1-v-2-u-3-v-4-u, which uses each of its eight edges once. A Hamiltonian cycle in a bipartite graph must alternate between its parts and therefore use the same number of vertices from each part. The parts of K2,4 have sizes 2 and 4, so no Hamiltonian cycle exists.

Second, take K4 on {A, B, C, D}, with edges {AB, AC, AD, BC, BD, CD}. All four degrees are 3, so it has neither an Euler trail nor an Euler circuit. Yet A-B-C-D-A is a Hamiltonian cycle.

Hamiltonian conditions: necessary filters versus sufficient theorems

Necessary filters for a Hamiltonian cycle are connectivity, minimum degree at least 2, and no cut vertex. They are not a complete test. In a bipartite graph, a Hamiltonian cycle alternates between the two parts, so their sizes must match. The unequal parts of K2,4 are therefore a valid obstruction, not merely a failed sufficient test.

Dirac's theorem: A simple graph on n >= 3 vertices is Hamiltonian if every vertex satisfies deg(v) >= n/2. For n = 8, minimum degree 4 meets the guarantee. Minimum degree 3 makes Dirac's test inconclusive, not negative.

Ore's theorem: A simple graph on n >= 3 vertices is Hamiltonian if every nonadjacent pair u, v satisfies deg(u) + deg(v) >= n.

Both are sufficient, not necessary; their converses are invalid.

Common traps and the correction for each

  1. Skipping connectivity. Two disjoint triangles ABC and DEF have edges {AB, BC, CA, DE, EF, FD}. Every degree is 2, but no single trail can cover both edge-containing components, so the whole graph has no Euler circuit.

  2. Calling two odd vertices an Euler circuit. Two odd vertices mean an open trail, with those vertices forced as endpoints. Zero odd vertices means a closed circuit.

  3. Rejecting a Hamiltonian cycle because edges remain unused. Vertices are compulsory, not edges. G's Hamiltonian cycle correctly leaves chords AC and CE unused.

  4. Using a sufficient theorem backwards. A failed Dirac or Ore test is inconclusive. A constructed cycle proves existence; non-existence needs a valid obstruction or a failed necessary condition.

How exam questions turn these ideas into decisions

Questions may ask you to classify a route, infer Euler status from degrees, find forced endpoints, choose a traversal, apply Dirac or Ore, or test an implication with a counterexample. The solved Graph Theory MCQs provide focused practice.

Use three passes:

  1. Write E for edge-once or V for vertex-once.

  2. For Euler, check edge connectivity and parity. For Hamiltonian, apply necessary filters or a sufficient theorem correctly.

  3. Construct a route and tick every required edge or vertex.

For example, in a stated connected graph with degree multiset (4, 4, 3, 3, 2, 2), the two degree-3 vertices are the only odd vertices. Therefore an open Euler trail exists, and those two vertices must be its endpoints.

Practise classification by deciding whether each graph has a trail, a circuit, a Hamiltonian path or a Hamiltonian cycle, and justify each answer with a witness or obstruction.

The short version and the next practice step

Euler means every edge once.

Hamiltonian means every vertex once.

Euler existence is controlled by edge connectivity and the odd-degree count.

Hamiltonian questions need construction, necessary filters, or a correctly applied sufficient theorem.

Without looking back, reclassify G, K2,4, K4, and the two-disjoint-triangles graph. Give one witness or obstruction for each. Then continue with GATE Guidance by Sanchit Sir or compare the wider GATE course options.