 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

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

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
Approx a minute

Which condition is required for an Eulerian trail to exist?

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

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

Outcomes

ACMGM085

explain 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; for example, the Königsberg Bridge problem, planning a garbage bin collection route

ACMGM086

explain the meaning of the terms: Hamiltonian graph and semi-Hamiltonian graph, and use these concepts to investigate and solve practical problems; for example, planning a sight-seeing tourist route around a city, the travelling-salesman problem (by trial-and-error methods only)