Eulerian and Hamiltonian Walks (HSC SSCE Mathematics Standard): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What must be true for a graph to contain an Eulerian circuit?
What must be true for a graph to contain an Eulerian circuit?
All vertices have even degree
How many vertices with odd degree are needed for an Eulerian trail to exist?
How many vertices with odd degree are needed for an Eulerian trail to exist?
Exactly 2
A connected graph has zero vertices with odd degree. What does it contain?
A connected graph has zero vertices with odd degree. What does it contain?
An Eulerian circuit
What is a Hamiltonian path?
What is a Hamiltonian path?
A path visiting every vertex once only
What is a Hamiltonian cycle?
What is a Hamiltonian cycle?
A Hamiltonian path starting & ending same
What is the key difference between Eulerian and Hamiltonian walks?
What is the key difference between Eulerian and Hamiltonian walks?
Eulerian focuses on edges, Hamiltonian on vertices
How can you identify if a Hamiltonian path exists in a graph?
How can you identify if a Hamiltonian path exists in a graph?
Careful inspection - no simple rule exists
Which real-world task is best suited to finding an Eulerian walk?
Which real-world task is best suited to finding an Eulerian walk?
Rubbish collection travelling every road
What might a Hamiltonian path NOT use?
What might a Hamiltonian path NOT use?
All the edges of the graph
In Eulerian walks, what can happen that cannot happen in Hamiltonian paths?
In Eulerian walks, what can happen that cannot happen in Hamiltonian paths?
Vertices may be visited more than once