{"id":1568,"date":"2023-04-11T15:12:03","date_gmt":"2023-04-11T15:12:03","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&p=1568"},"modified":"2025-08-29T04:41:27","modified_gmt":"2025-08-29T04:41:27","slug":"euler-and-hamiltonian-paths-and-circuits-learn-it-3","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-learn-it-3\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Learn It 3","rendered":"Euler and Hamiltonian Paths and Circuits: Learn It 3"},"content":{"raw":"

Hamiltonian Circuits<\/h2>\r\n

We just learned how to optimize a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.<\/p>\r\n

\r\n
\r\n

Hamiltonian circuits<\/h3>\r\n

A Hamiltonian circuit<\/strong> is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex.<\/p>\r\n<\/div>\r\n<\/section>\r\n

\r\n

It is important to remember that Euler circuits visit all edges without repetition, while Hamilton circuits visit all vertices without repetition. To help you remember, think of the E<\/em> in Euler as standing for Edge.<\/p>\r\n<\/section>\r\n

One Hamiltonian circuit is shown on the graph below. There are several other Hamiltonian circuits possible on this graph. Notice that the circuit only has to visit every vertex once; it does not need to use every edge.<\/p>\r\n

This circuit could be notated by the sequence of vertices visited, starting and ending at the same vertex: [latex]ABFGCDHMLKJEA[\/latex]. Notice that the same circuit could be written in reverse order, or starting and ending at a different vertex.<\/p>\r\n

\r\n[caption id=\"attachment_6225\" align=\"aligncenter\" width=\"500\"]\"Rectangular Figure 1. A circuit notated with a sequence of vertices ending at one vertex: [latex]ABFGCDHMLKJEA[\/latex][\/caption]\r\n<\/center>\r\n

 <\/p>\r\n

Unlike with Euler circuits, there is no nice theorem that allows us to instantly determine whether or not a Hamiltonian circuit exists for all graphs.[footnote]There are some theorems that can be used in specific circumstances, such as Dirac\u2019s theorem, which says that a Hamiltonian circuit must exist on a graph with [latex]n[\/latex] vertices if each vertex has degree [latex]n\/2[\/latex] or greater.[\/footnote]<\/p>\r\n

Does a Hamiltonian circuit exist on the graph below?
\"Arrow<\/center>[reveal-answer q=\"997648\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997648\"] We can see that once we travel to vertex [latex]E[\/latex] there is no way to leave without returning to [latex]C[\/latex], so there is no possibility of a Hamiltonian circuit. [\/hidden-answer]<\/section>\r\n
[ohm2_question hide_question_numbers=1]6962[\/ohm2_question]<\/section>\r\n

Hamiltonian Paths<\/h2>\r\n
\r\n
\r\n

Hamiltonian paths<\/h3>\r\n

A Hamiltonian path<\/strong> visits every vertex once with no repeats, but does not have to start and end at the same vertex.<\/p>\r\n<\/div>\r\n<\/section>\r\n

\r\n

Since a Hamilton path visits each vertex exactly once, it must have the same number of vertices listed as appear in the graph.<\/p>\r\n<\/section>\r\n

Use the graph below to find a Hamilton path between vertices [latex]C[\/latex] and [latex]D[\/latex].
\"Graph<\/center>[reveal-answer q=\"997641\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997641\"] If we start at vertex [latex]C[\/latex], [latex]A[\/latex] must be next. Then we must choose between [latex]B[\/latex] and [latex]F[\/latex]. If we choose [latex]F[\/latex], we will have to backtrack to get to include [latex]B[\/latex]; so, we must choose [latex]B[\/latex]. Once we choose [latex]B[\/latex], we must choose [latex]F[\/latex] next. After [latex]F[\/latex], we choose [latex]E[\/latex], because we want to end at [latex]D[\/latex]. So, a Hamilton path between [latex]C[\/latex] and [latex]D[\/latex] is [latex]C \u2192 A \u2192 B \u2192 F \u2192 E \u2192 D[\/latex]. [\/hidden-answer]<\/section>\r\n

There is not a short way to determine if there is a Hamilton path between two vertices on a graph that works in every situation. However, there are a few common situations that can help us to quickly determine that there is no Hamilton path. Some of these are listed in the table below.<\/p>\r\n

\r\n\r\n\r\n\r\n\r\n\r\n\r\n
Scenario<\/strong>\u00a0<\/td>\r\nDiagram<\/strong>\u00a0<\/td>\r\n<\/tr>\r\n
If an edge [latex]ab[\/latex] is a bridge, then there is no Hamilton path between a pair of vertices that are on the same side of edge [latex]ab[\/latex].<\/td>\r\n\"A\r\n

No Hamilton path between any two vertices in the component [latex]{a, c, d, f}[\/latex]. No Hamilton path between any two vertices in [latex]{b, e, h, g, i}[\/latex].<\/p>\r\n\r\n\u00a0<\/td>\r\n<\/tr>\r\n

If an edge [latex]ab[\/latex] is a bridge with at least three components on each side, then there is no Hamilton path beginning or ending at [latex]a[\/latex] or [latex]b[\/latex].\u00a0<\/td>\r\n\"A\r\n

No Hamilton path beginning or ending at [latex]a[\/latex] or [latex]b[\/latex].<\/p>\r\n\r\n\u00a0\u00a0<\/td>\r\n<\/tr>\r\n

If a graph is composed of two cycles joined only at a single vertex [latex]p[\/latex], and [latex]v[\/latex] is any vertex that is NOT adjacent to [latex]p[\/latex], then there are no Hamilton paths beginning or ending at [latex]p[\/latex].<\/td>\r\n\"A\r\n

\u00a0No Hamilton path can be formed starting or ending at vertices, [latex]r[\/latex], [latex]v[\/latex], or [latex]u[\/latex] because they are not adjacent to [latex]p[\/latex].<\/p>\r\n\r\n\u00a0<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/section>\r\n

\r\n

There are also many other situations in which a Hamilton path is not possible. These are just a few that you will encounter.<\/p>\r\n<\/section>","rendered":"

Hamiltonian Circuits<\/h2>\n

We just learned how to optimize a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.<\/p>\n

\n
\n

Hamiltonian circuits<\/h3>\n

A Hamiltonian circuit<\/strong> is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex.<\/p>\n<\/div>\n<\/section>\n

\n

It is important to remember that Euler circuits visit all edges without repetition, while Hamilton circuits visit all vertices without repetition. To help you remember, think of the E<\/em> in Euler as standing for Edge.<\/p>\n<\/section>\n

One Hamiltonian circuit is shown on the graph below. There are several other Hamiltonian circuits possible on this graph. Notice that the circuit only has to visit every vertex once; it does not need to use every edge.<\/p>\n

This circuit could be notated by the sequence of vertices visited, starting and ending at the same vertex: [latex]ABFGCDHMLKJEA[\/latex]. Notice that the same circuit could be written in reverse order, or starting and ending at a different vertex.<\/p>\n

\n
\"Rectangular
Figure 1. A circuit notated with a sequence of vertices ending at one vertex: [latex]ABFGCDHMLKJEA[\/latex]<\/figcaption><\/figure>\n<\/div>\n

 <\/p>\n

Unlike with Euler circuits, there is no nice theorem that allows us to instantly determine whether or not a Hamiltonian circuit exists for all graphs.[1]<\/sup><\/a><\/p>\n

Does a Hamiltonian circuit exist on the graph below?<\/p>\n
\"Arrow<\/div>\n