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

3.3.8

demonstrate the meanings of, and use, 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

3.3.9

demonstrate the meanings of, and use, the terms: Hamiltonian graph and semi-Hamiltonian graph, and use these concepts to investigate and solve practical problems

What is Mathspace

About Mathspace