Q10Discrete Mathematics Structure
Question
2 marks
What is the difference between path and circuit? Define Hamiltonian path and circuit.
Answer
Paths do not repeat vertices/edges; circuits are closed paths. Hamiltonian visits every vertex.
- Path: A sequence of edges where no vertex (and thus no edge) is repeated.
- Circuit: A closed path (starts and ends at the same vertex).
- Hamiltonian Path: A path that visits every vertex in the graph exactly once.
- Hamiltonian Circuit: A circuit that visits every vertex exactly once and returns to the start.