Graphs · step 5 of 14

Euler & Hamilton paths and circuits

An Euler circuit uses every EDGE exactly once; a Hamilton cycle visits every VERTEX exactly once. The contrast is stark: Euler has a clean criterion — connected with all degrees even — checkable in linear time, while deciding Hamiltonicity is NP-complete with only sufficient conditions like Dirac’s available.

Practise euler & hamilton paths and circuits free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Euler circuit — check degreesConnected (ignoring isolated vertices) and every vertex of even degree. That is necessary and sufficient.
Euler path — allow two oddExactly two odd-degree vertices gives an Euler path, and it must start at one and end at the other.
Hamilton — try Dirac or OreIf every vertex has degree ≥ n/2 (Dirac), a Hamilton cycle exists. These are sufficient, never necessary.
Refute Hamiltonicity structurallyFind a cut vertex, or a set S whose removal leaves more than |S| components — either forbids a Hamilton cycle.

Worked example

A graph has degree sequence (2, 2, 3, 3, 4) and is connected. Does it have an Euler circuit? An Euler path?

Sum of degrees is 14, so there are 7 edges.
Odd-degree vertices: the two of degree 3 — exactly two.
An Euler circuit needs zero odd vertices, so there is none.
Exactly two odd vertices with connectivity gives an Euler path.

Answer. No Euler circuit, but an Euler path exists, starting at one degree-3 vertex and ending at the other.

Where marks get dropped

These are the specific errors that cost credit on euler & hamilton paths and circuits questions — QED's rubric penalises each of them separately.

Confusing Euler with Hamilton. Euler is about edges and easy; Hamilton is about vertices and hard.
Applying Dirac’s condition in reverse. Failing it does not mean there is no Hamilton cycle — C₅ has all degrees 2 < 2.5 yet is Hamiltonian.
Forgetting connectivity in the Euler criterion. All-even degrees in a disconnected graph give no Euler circuit.

Practise this until it is automatic

Unlimited fresh questions

QED generates new euler & hamilton paths and circuits problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Euler & Hamilton paths and circuits — frequently asked questions

What was the Königsberg bridge problem?

Euler showed the four landmasses all had odd degree, so no walk could cross all seven bridges once — the founding result of graph theory.

Is there a Hamilton criterion like Euler’s?

No known efficient one — the decision problem is NP-complete. Dirac’s and Ore’s conditions are sufficient only.

Can a graph have both an Euler and a Hamilton circuit?

Yes. C₄ has all degrees 2 (even, so Eulerian) and is obviously Hamiltonian. The two properties are independent in general.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make euler & hamilton paths and circuits exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →