Chapter 6 Test: Euler and Hamilton Circuits and Paths

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.

Front

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

Back

All vertices must have even degrees.

Front

What is a Euler's Path?

Back

A Euler's Path is a path in a graph that visits every edge exactly once but does not necessarily return to the starting vertex.

Front

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

Back

Exactly two vertices must have odd degrees.

Front

What is a Hamiltonian Circuit?

Back

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

Front

What is a Hamiltonian Path?

Back

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

Front

How do you determine if a graph has a Hamiltonian Circuit?

Back

There is no simple condition; it often requires checking various paths.

Front

What is the difference between Euler's and Hamiltonian paths?

Back

Euler's paths focus on edges, while Hamiltonian paths focus on vertices.

Front

What is the complete graph K_n?

Back

K_n is a complete graph with n vertices where every pair of distinct vertices is connected by a unique edge.

Front

How many edges does K_n have?

Back

K_n has n(n-1)/2 edges.