Paths & Connectivity

Definition

Paths and Circuits

A walk is a sequence of vertices where consecutive vertices are adjacent. A path is a walk with no repeated vertices. A circuit (cycle) is a walk that starts and ends at the same vertex with no other repeated vertices.

The length of a path or circuit is the number of edges it contains.

Definition

Connectivity

A graph is connected if there is a path between every pair of vertices. A connected component is a maximal connected subgraph.

In a directed graph, strong connectivity means there is a directed path from u to v AND from v to u for every pair of vertices.

Definition

Euler Paths and Circuits

An Euler path traverses every EDGE exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex.

Theorem (Euler): • A connected graph has an Euler circuit ⟺ every vertex has even degree. • A connected graph has an Euler path (but not circuit) ⟺ it has exactly 2 vertices with odd degree.

Example

Euler Circuit Example

The Konigsberg Bridge Problem: The city had 4 land masses connected by 7 bridges. Euler showed no walk could cross each bridge exactly once because more than 2 land masses had odd degree. This problem gave birth to graph theory in 1736!

Definition

Hamilton Paths and Circuits

A Hamilton path visits every VERTEX exactly once. A Hamilton circuit is a Hamilton path that returns to the starting vertex.

Unlike Euler paths, there is no simple characterization of which graphs have Hamilton paths. Determining whether a Hamilton path exists is an NP-complete problem.

Theorem

Dirac's Theorem

If G is a simple graph with n ≥ 3 vertices and every vertex has degree ≥ n/2, then G has a Hamilton circuit.

This is a sufficient condition, not a necessary one - graphs can have Hamilton circuits without meeting Dirac's condition.