Euler and Hamilton Paths and Circuits

Front

What is an Euler Path?

Back

An Euler Path is a trail in a graph that visits every edge exactly once but may visit vertices more than once.

Front

What is an Euler Circuit?

Back

An Euler Circuit is a trail in a graph that visits every edge exactly once and starts and ends at the same vertex.

Front

What condition must be met for a graph to have an Euler Circuit?

Back

A graph must have all vertices of even degree to have an Euler Circuit.

Front

What condition must be met for a graph to have an Euler Path?

Back

A graph must have exactly zero or two vertices of odd degree to have an Euler Path.

Front

What is a Hamilton Path?

Back

A Hamilton Path is a path in a graph that visits every vertex exactly once.

Front

What is a Hamilton Circuit?

Back

A Hamilton Circuit is a circuit in a graph that visits every vertex exactly once and returns to the starting vertex.

Front

Can a graph have both an Euler Circuit and a Hamilton Circuit?

Back

Yes, a graph can have both an Euler Circuit and a Hamilton Circuit, but the conditions for each are different.

Front

What is the significance of odd degree vertices in Euler Paths?

Back

A graph can have an Euler Path if it has exactly two vertices of odd degree.

Front

True or False: A graph with one odd vertex can have an Euler Circuit.

Back

False.

Front

True or False: A graph with all even degree vertices has an Euler Circuit.

Back

True.