Graph Theory Review: Lessons 1-4

Path/Chain = A series of vertices connected via edges.

Cycles/Circuits = A path that starts and ends at the same vertex.

Simple = A path/circuit with no repeated edges

​

Paths and Cycles

​Using the graph below,

ABCD is a path

ABCDEA is a cycle

ABC is a simple path

ABEA is a simple cycle

ABCB is NOT a simple path

Euler Path = Cross ALL edges once

• Must be a connected graph

• Exactly two vertices have an odd degree

• Start and end at these two odd-degree vertices

​

​Types of Paths

Hamilton Path = Cross ALL vertices once

• Must be a connected graph

• Doesn't matter where you start or end

Using the graph below,

Euler Path = BAEDCBE

Hamilton Path = ABCDE

Euler Cycle = Cross ALL edges

• Must be connected

• All vertices must have EVEN degrees

• Start and end at the same vertex

​

Types of Cycles

​Hamilton Cycle = Cross ALL vertices

• Must be connected

• All vertices must have degrees greater than 1

​Using the graph below,

Euler Cycle= ABCDEACEBDA

Hamilton Cycle = ABCDEA