Discrete Structure (BSc CSIT, CSC160): the questions likely to come

Euler and Hamiltonian Paths and Circuits

Euler Path and Euler Circuit

• An Euler path is a path that traverses every edge of the graph exactly once (vertices may repeat).
• An Euler circuit is an Euler path that starts and ends at the same vertex, i.e. a closed Euler path.

Example. In the graph with vertices $\{A,B,C,D\}$ and edges $AB, BC, CD, DA, AC$:

• $D{-}A{-}B{-}C{-}A{-}C$? — instead, $A{-}B{-}C{-}D{-}A{-}C$ is an Euler path (uses each of the 5 edges once) but not a circuit, because it starts at $A$ and ends at $C$. (Here $A$ and $C$ have odd degree.)

Hamiltonian Path and Hamiltonian Circuit

• A Hamiltonian path visits every vertex exactly once (edges may be skipped).
• A Hamiltonian circuit (cycle) is a Hamiltonian path that returns to the starting vertex, visiting every vertex exactly once and closing the loop.

Example. In the cycle graph $C_4$ with vertices $A,B,C,D$ and edges $AB, BC, CD, DA$, the sequence $A{-}B{-}C{-}D{-}A$ is a Hamiltonian circuit (every vertex once, returns to $A$).

Key Difference

Necessary and Sufficient Conditions for an Euler Circuit

Theorem (Euler). A connected graph $G$ has an Euler circuit if and only if every vertex has even degree.

Related condition for an Euler path (open): a connected graph has an Euler path that is not a circuit if and only if it has exactly two vertices of odd degree (the path begins at one and ends at the other).

Reasoning: each time the trail enters a vertex it must also leave it, pairing up edges at that vertex; for a closed circuit this forces every degree to be even.