topic badge

4.05 Eulerian and Hamiltonian graphs

Interactive practice questions

The following questions relate to Eulerian trails and semi-Eulerian trails.

a

Which of the following is a correct description of an Eulerian trail?

A trail that passes through each edge of a graph at least once.

A

A trail that passes through each edge of a graph exactly once and starts and finishes at the same vertex.

B

A trail that visits each edge and each vertex once only.

C

A closed trail that visits each vertex exactly once.

D
b

Which of the following is a correct description of a semi-Eulerian trail?

An Eulerian trail that starts and finishes at the same vertex.

A

An Eulerian trail that visits each vertex exactly once.

B

A trail that passes through each vertex of the graph and starts and finishes at a different vertex.

C

A trail that passes through each edge of the graph and starts and finishes at a different vertex.

D
Easy
1min

Which condition is required for an Eulerian trail to exist?

Easy
< 1min

Which condition is required for a semi-Eulerian trail to exist?

Easy
< 1min

In order to traverse a graph which has an Eulerian trail, which vertex should one start at?

Easy
< 1min
Sign up to access Practice Questions
Get full access to our content with a Mathspace account

Outcomes

4.2.2.5

understand the meaning of the terms Eulerian graph, Eulerian trail, semi-Eulerian graph, semi-Eulerian trail and the conditions for their existence, and use these concepts to investigate and solve practical problems, e.g. the Königsberg bridge problem, planning a garbage bin collection route

4.2.2.6

understand the meaning of the terms Hamiltonian graph and semi-Hamiltonian graph and use these concepts to investigate and solve practical problems (by trial-and-error methods only), e.g. planning a sightseeing tourist route around a city, the travelling-salesman problem

What is Mathspace

About Mathspace