Paths and Cycles

Connectivity is defined by the existence of paths.

Definitions

Walk: A sequence of vertices $v_{1}, v_{2}, \dots, v_{k}$ where $v_{i} v_{i + 1}$ is an edge.
Path: A walk with no repeated vertices.
Cycle: A walk with no repeated vertices except $v_{1} = v_{k}$ .

A trail that visits every edge exactly once and returns to the start.

Theorem (Euler's Theorem)

A connected graph has an Eulerian circuit if and only if every vertex has an even degree.

A cycle that visits every vertex exactly once.

No simple necessary/sufficient condition exists (NP-complete problem).
Dirac's Theorem: If $n \geq 3$ and $de g (v) \geq n /2$ for all $v$ , then $G$ has a Hamiltonian cycle.

Exercise (Problem 1)

Can you draw a continuous line that crosses every segment of the figure below exactly once? (Bridges of Königsberg).

Exercise (Problem 2)

Prove that a graph with

n

vertices and

n

edges must contain a cycle.

Exercise (Problem 3)

If a graph contains a cycle of length

k

, prove it contains a path of length at least

k - 1