Neural Sync Active

Eulerian and Hamiltonian Paths

Registry Synced

Eulerian and Hamiltonian Paths

233 words

1 min read

Reading compass

Now · 7.1 Eulerian Trails

Eulerian and Hamiltonian Paths

7.1 Eulerian Trails

An Eulerian trail uses every edge exactly once. An Eulerian circuit starts and ends at the same vertex.

Euler's Theorem

A connected graph has an Eulerian circuit iff all vertices have even degree.
A connected graph has an Eulerian trail (not circuit) iff exactly two vertices have odd degree.

7.2 Hamiltonian Paths

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle starts and ends at the same vertex.

Dirac's Theorem

G

is a graph with

n \geq 3

vertices and every vertex has degree

\geq n/2

, then

G

has a Hamiltonian cycle.

Ore's Theorem

G

is a graph with

n \geq 3

and

\deg(u) + \deg(v) \geq n

for every non-adjacent pair

u,v

, then

G

has a Hamiltonian cycle.

✅ Practice Questions

Q1: Does

K_5

have an Eulerian circuit? A Hamiltonian cycle?

Solution

$K_5$ : every vertex has degree 4 (even), so Eulerian circuit exists. Since $n=5 \geq 3$ and $\deg(v)=4 \geq 5/2$ , by Dirac, Hamiltonian cycle exists. Q2: The Königsberg bridge problem — 7 bridges connecting 4 land masses. Does an Eulerian trail exist? Solution

The graph had 4 vertices with degrees 3,3,3,3 (all odd). Exactly 4 odd-degree vertices (not 0 or 2), so no Eulerian trail exists. Join Discord PreviousGraph Coloring AppsNextGraph Algorithms