Graph Theory Review

Front

What is a Euler's Circuit?

Back

A Euler's Circuit is a path in a graph that visits every edge exactly once and returns to the starting vertex. For a graph to have a Euler's Circuit, all vertices must have even degrees.

Front

What is a Hamilton Path?

Back

A Hamilton Path is a path in a graph that visits every vertex exactly once. It does not need to return to the starting vertex.

Front

What is the condition for a graph to have a Euler Path?

Back

A graph has a Euler Path if it has exactly 0 or 2 vertices of odd degree.

Front

What is a circuit in graph theory?

Back

A circuit is a closed path in a graph where the starting and ending vertices are the same, and it visits every edge exactly once.

Front

What is the difference between a Euler Path and a Hamilton Path?

Back

A Euler Path visits every edge exactly once, while a Hamilton Path visits every vertex exactly once.

Front

What does it mean for a vertex to have an even degree?

Back

A vertex has an even degree if it is connected to an even number of edges.

Front

What does it mean for a vertex to have an odd degree?

Back

A vertex has an odd degree if it is connected to an odd number of edges.

Front

Can a Hamilton Path skip vertices?

Back

Yes, a Hamilton Path can skip vertices, but it must visit every vertex exactly once.

Front

What is the significance of the starting and ending vertex in a Hamilton Circuit?

Back

In a Hamilton Circuit, the path must start and end at the same vertex, visiting every other vertex exactly once.

Front

What is the minimum distance in a Hamilton Path problem?

Back

The minimum distance in a Hamilton Path problem is the shortest possible path that visits each vertex exactly once.