MA19.FM.17

Students understand that:

• Graphs can be used to model real-world problems and Hamilton and Euler circuits and paths can provide solutions to such problems.
• An Euler circuit cannot exist in a graph with any odd degree vertices.
• An Euler path cannot exist in a graph without exactly two odd degree vertices.
• No known good algorithm has been established for finding a Hamilton path or circuit since no necessary and sufficient conditions for the existence of a Hamilton path or circuit have been identified.
• The graph must be connected in order for a Hamilton or Euler path or circuit to exist.