{"id":1555,"date":"2023-04-11T14:52:58","date_gmt":"2023-04-11T14:52:58","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=1555"},"modified":"2024-10-18T20:58:09","modified_gmt":"2024-10-18T20:58:09","slug":"euler-and-hamiltonian-paths-and-circuits-learn-it-2","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-learn-it-2\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Learn It 2","rendered":"Euler and Hamiltonian Paths and Circuits: Learn It 2"},"content":{"raw":"<h2>Fleury\u2019s Algorithm<\/h2>\r\n<p>Now we know how to determine if a graph has an Euler circuit, how can we find an Euler circuit in the graph? While it usually is possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury\u2019s algorithm.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Fleury\u2019s Algorithm<\/h3>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Start at any vertex if finding an Euler circuit. If finding an Euler path, start at one of the two vertices with odd degree.<\/li>\r\n\t<li>Choose any edge leaving your current vertex, provided deleting that edge will not separate the graph into two disconnected sets of edges.<\/li>\r\n\t<li>Add that edge to your circuit, and delete it from the graph.<\/li>\r\n\t<li>Continue until you\u2019re done.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox example\">Find an Euler Circuit on this graph using Fleury\u2019s algorithm, starting at vertex [latex]A[\/latex].<center><img class=\"alignnone wp-image-12912 size-full\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits.png\" alt=\"Step 1: Original Graph. Choosing edge AD. Circuit so far: AD. Step 2: AD deleted. D is current. Can\u2019t choose DC since that would disconnect graph. Choosing DE.Circuit so far: ADE. Step 3: E is current. From here, there is only one option, so the rest of the circuit is determined. Circuit: ADEBDCA.\" width=\"788\" height=\"361\" \/><\/center>\u00a0<\/section>\r\n<p>The following video presents more examples of using Fleury\u2019s algorithm to find an Euler Circuit.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/vvP4Fg4r-Ns\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Fleury's+Algorthim.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Fleury's Algorthim\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h3>Eulerization<\/h3>\r\n<p>Not every graph has an Euler path or circuit. In order to create a Euler circuit on a graph we use a process known as <strong>Eulerization <\/strong>.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Eulerization<\/h3>\r\n<p><strong>Eulerization <\/strong>is the process of adding edges to a graph to create an Euler circuit on a graph.<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>To eulerize a graph, edges are duplicated to connect pairs of vertices with odd degree. Connecting two odd degree vertices increases the degree of each, giving them both even degree. When two odd degree vertices are not directly connected, we can duplicate all edges in a path connecting the two.<\/p>\r\n<\/div>\r\n<\/section>\r\n<p>Note that we can only duplicate edges, not create edges where there wasn\u2019t one before. Duplicating edges would mean walking or driving down a road twice, while creating an edge where there wasn\u2019t one before is akin to installing a new road!<\/p>\r\n<section class=\"textbox example\">For the rectangular graph shown, three possible eulerizations are shown. Notice in each of these cases the vertices that started with odd degrees have even degrees after eulerization, allowing for an Euler circuit.\r\n\r\n<div><center><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\"><img class=\"alignnone size-full wp-image-1830\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\" alt=\"2 by 4 grid of rectangles. Each intersection has an open dot.\" width=\"137\" height=\"51\" \/><\/a><\/center><center><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\"><img class=\"alignnone wp-image-1831 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, lower dots on cell 2:2, upper dots on cell 2:2, upper dots on cell 1:2, and upper dots on cell 2:3\" width=\"136\" height=\"60\" \/><\/a><\/center><center><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\"><img class=\"alignnone wp-image-1832 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, right-hand dots on cell 1:1, upper dots on cell 1:3, right-hand dots on cell 1:3, and lower dots on cell 2:2\" width=\"143\" height=\"61\" \/><\/a><\/center><center><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\"><img class=\"alignnone wp-image-1833 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, right-hand dots on cell 2:1, right-hand dots on cell 1:1, upper dots on cell 2:2, right-hand dots on cell 2:2, right-hand dots on cell 1:2, upper dots on cell 2:3\" width=\"137\" height=\"56\" \/><\/a><\/center><\/div>\r\n<\/section>\r\n<p>In the example above, you\u2019ll notice that the last eulerization required duplicating seven edges, while the first two only required duplicating five edges. If we were eulerizing the graph to find a walking path, we would want the eulerization with minimal duplications. If the edges had weights representing distances or costs, then we would want to select the eulerization with the minimal total added weight.\u00a0<\/p>\r\n<section class=\"textbox proTip\">\r\n<p><strong>IMPORTANT!<\/strong> Since only duplicate edges can be added to eulerize a graph, it is not possible to eulerize a disconnected graph.<\/p>\r\n<\/section>\r\n<section class=\"textbox example\">\r\n<p>Use Graph [latex]A[\/latex] and multigraphs [latex]B, C, D,[\/latex] and [latex]E[\/latex] given in figure below to answer the questions.<\/p>\r\n<center><img class=\"wp-image-8768 size-large\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-1024x353.png\" alt=\"Five graphs. Each graph has five vertices, a to e. Graph A: edge F, a to c. Edge H, a to d. Edge G, a to b. Edge I, b to c. Edge J, b to d. Edge K, c to e. Edge L, d to e. Multigraph B: edge F, a to c. Edge H, a to d. Edges G and M, a to b. Edge I, b to c. Edge J, b to d. Edge N, c to d. Edge K, c to e. Edge L, d to e. Multigraph C: edge F, a to c. Edge H, a to d. Edges M and G, a to b. Edges I and P, b to c. Edges J and Q, b to d. Edge K, c to e. Edge L, d to e. Multigraph D: edge F, a to c. Edges H and A, a to d. Edge G, a to b. Edges P and I, b to c. Edge J, b to d. Edge K, c to e. Edge L, d to e. Multigraph E: edge F, a to c. Edge H, a to d. Edge I, b to c. Edges J and a, b to d. Edges K and S, c ad e. Edge L, d to e.\" width=\"1024\" height=\"353\" \/><\/center><center><strong><span style=\"font-size: 10pt;\">Graph A and Multigraphs B through E<\/span><\/strong><\/center>\r\n<p>&nbsp;<\/p>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Which of the multigraphs are not eulerizations of Graph [latex]A[\/latex]? Explain your answer.<\/li>\r\n\t<li>Which eulerization of Graph [latex]A[\/latex] uses the fewest duplicate edges? How many does it use?<\/li>\r\n\t<li>Is it possible to eulerize Graph [latex]A[\/latex] using fewer duplicate edges than your answer to part 2? If so, give an example. If not, explain why not.<\/li>\r\n<\/ol>\r\n\r\n[reveal-answer q=\"197648\"]Show Solution[\/reveal-answer] [hidden-answer a=\"197648\"]\r\n\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Multigraph [latex]B[\/latex] is not an eulerization of [latex]A[\/latex] because the edge [latex]N[\/latex] between vertices [latex]c[\/latex] and [latex]d[\/latex] is not a duplicate of an existing edge. Multigraph [latex]E[\/latex] is not an eulerization of [latex]A[\/latex] because vertices [latex]b[\/latex] and [latex]e[\/latex] have odd degree.<\/li>\r\n\t<li>Multigraph [latex]C[\/latex] uses [latex]3[\/latex] duplicate edges while multigraph [latex]D[\/latex] only uses [latex]2[\/latex]. So, [latex]D[\/latex] uses the fewest.<\/li>\r\n\t<li>Since there were four vertices in Graph [latex]A[\/latex], the fewest number of edges that could possibly eulerize the graph is half of four, which is two. So, it is not possible to eulerize Graph [latex]A[\/latex] using fewer edges.<\/li>\r\n<\/ol>\r\n\r\n[\/hidden-answer]<\/section>\r\n<section class=\"textbox proTip\">\r\n<p>It's important to note that the process of eulerization should respect the rule that only existing edges can be duplicated; new edges cannot be created where there wasn't one before.<\/p>\r\n<\/section>\r\n<p>The problem of finding the optimal eulerization is called the Chinese Postman Problem, a name given by an American in honor of the Chinese mathematician Mei-Ko Kwan who first studied the problem in 1962 while trying to find optimal delivery routes for postal carriers. \u00a0This problem is important in determining efficient routes for garbage trucks, school buses, parking meter checkers, street sweepers, and more.<\/p>","rendered":"<h2>Fleury\u2019s Algorithm<\/h2>\n<p>Now we know how to determine if a graph has an Euler circuit, how can we find an Euler circuit in the graph? While it usually is possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury\u2019s algorithm.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>Fleury\u2019s Algorithm<\/h3>\n<ol style=\"list-style-type: decimal;\">\n<li>Start at any vertex if finding an Euler circuit. If finding an Euler path, start at one of the two vertices with odd degree.<\/li>\n<li>Choose any edge leaving your current vertex, provided deleting that edge will not separate the graph into two disconnected sets of edges.<\/li>\n<li>Add that edge to your circuit, and delete it from the graph.<\/li>\n<li>Continue until you\u2019re done.<\/li>\n<\/ol>\n<\/div>\n<\/section>\n<section class=\"textbox example\">Find an Euler Circuit on this graph using Fleury\u2019s algorithm, starting at vertex [latex]A[\/latex].<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-12912 size-full\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits.png\" alt=\"Step 1: Original Graph. Choosing edge AD. Circuit so far: AD. Step 2: AD deleted. D is current. Can\u2019t choose DC since that would disconnect graph. Choosing DE.Circuit so far: ADE. Step 3: E is current. From here, there is only one option, so the rest of the circuit is determined. Circuit: ADEBDCA.\" width=\"788\" height=\"361\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits.png 788w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits-300x137.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits-768x352.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits-65x30.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits-225x103.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12181441\/large-3Circuits-350x160.png 350w\" sizes=\"(max-width: 788px) 100vw, 788px\" \/><\/div>\n<p>\u00a0<\/section>\n<p>The following video presents more examples of using Fleury\u2019s algorithm to find an Euler Circuit.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/vvP4Fg4r-Ns\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Fleury's+Algorthim.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Fleury&#8217;s Algorthim\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h3>Eulerization<\/h3>\n<p>Not every graph has an Euler path or circuit. In order to create a Euler circuit on a graph we use a process known as <strong>Eulerization <\/strong>.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>Eulerization<\/h3>\n<p><strong>Eulerization <\/strong>is the process of adding edges to a graph to create an Euler circuit on a graph.<\/p>\n<p>&nbsp;<\/p>\n<p>To eulerize a graph, edges are duplicated to connect pairs of vertices with odd degree. Connecting two odd degree vertices increases the degree of each, giving them both even degree. When two odd degree vertices are not directly connected, we can duplicate all edges in a path connecting the two.<\/p>\n<\/div>\n<\/section>\n<p>Note that we can only duplicate edges, not create edges where there wasn\u2019t one before. Duplicating edges would mean walking or driving down a road twice, while creating an edge where there wasn\u2019t one before is akin to installing a new road!<\/p>\n<section class=\"textbox example\">For the rectangular graph shown, three possible eulerizations are shown. Notice in each of these cases the vertices that started with odd degrees have even degrees after eulerization, allowing for an Euler circuit.<\/p>\n<div>\n<div style=\"text-align: center;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1830\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\" alt=\"2 by 4 grid of rectangles. Each intersection has an open dot.\" width=\"137\" height=\"51\" \/><\/a><\/div>\n<div style=\"text-align: center;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1831 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, lower dots on cell 2:2, upper dots on cell 2:2, upper dots on cell 1:2, and upper dots on cell 2:3\" width=\"136\" height=\"60\" \/><\/a><\/div>\n<div style=\"text-align: center;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1832 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, right-hand dots on cell 1:1, upper dots on cell 1:3, right-hand dots on cell 1:3, and lower dots on cell 2:2\" width=\"143\" height=\"61\" \/><\/a><\/div>\n<div style=\"text-align: center;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1833 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, right-hand dots on cell 2:1, right-hand dots on cell 1:1, upper dots on cell 2:2, right-hand dots on cell 2:2, right-hand dots on cell 1:2, upper dots on cell 2:3\" width=\"137\" height=\"56\" \/><\/a><\/div>\n<\/div>\n<\/section>\n<p>In the example above, you\u2019ll notice that the last eulerization required duplicating seven edges, while the first two only required duplicating five edges. If we were eulerizing the graph to find a walking path, we would want the eulerization with minimal duplications. If the edges had weights representing distances or costs, then we would want to select the eulerization with the minimal total added weight.\u00a0<\/p>\n<section class=\"textbox proTip\">\n<p><strong>IMPORTANT!<\/strong> Since only duplicate edges can be added to eulerize a graph, it is not possible to eulerize a disconnected graph.<\/p>\n<\/section>\n<section class=\"textbox example\">\n<p>Use Graph [latex]A[\/latex] and multigraphs [latex]B, C, D,[\/latex] and [latex]E[\/latex] given in figure below to answer the questions.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-8768 size-large\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-1024x353.png\" alt=\"Five graphs. Each graph has five vertices, a to e. Graph A: edge F, a to c. Edge H, a to d. Edge G, a to b. Edge I, b to c. Edge J, b to d. Edge K, c to e. Edge L, d to e. Multigraph B: edge F, a to c. Edge H, a to d. Edges G and M, a to b. Edge I, b to c. Edge J, b to d. Edge N, c to d. Edge K, c to e. Edge L, d to e. Multigraph C: edge F, a to c. Edge H, a to d. Edges M and G, a to b. Edges I and P, b to c. Edges J and Q, b to d. Edge K, c to e. Edge L, d to e. Multigraph D: edge F, a to c. Edges H and A, a to d. Edge G, a to b. Edges P and I, b to c. Edge J, b to d. Edge K, c to e. Edge L, d to e. Multigraph E: edge F, a to c. Edge H, a to d. Edge I, b to c. Edges J and a, b to d. Edges K and S, c ad e. Edge L, d to e.\" width=\"1024\" height=\"353\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-1024x353.png 1024w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-300x103.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-768x265.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-1536x529.png 1536w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-1200x413.png 1200w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-65x22.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-225x77.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7-350x121.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05161418\/36abc98c1f8fcd473fc2aa1395bdf6ab526d9ed7.png 1742w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/div>\n<div style=\"text-align: center;\"><strong><span style=\"font-size: 10pt;\">Graph A and Multigraphs B through E<\/span><\/strong><\/div>\n<p>&nbsp;<\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>Which of the multigraphs are not eulerizations of Graph [latex]A[\/latex]? Explain your answer.<\/li>\n<li>Which eulerization of Graph [latex]A[\/latex] uses the fewest duplicate edges? How many does it use?<\/li>\n<li>Is it possible to eulerize Graph [latex]A[\/latex] using fewer duplicate edges than your answer to part 2? If so, give an example. If not, explain why not.<\/li>\n<\/ol>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q197648\">Show Solution<\/button> <\/p>\n<div id=\"q197648\" class=\"hidden-answer\" style=\"display: none\">\n<ol style=\"list-style-type: decimal;\">\n<li>Multigraph [latex]B[\/latex] is not an eulerization of [latex]A[\/latex] because the edge [latex]N[\/latex] between vertices [latex]c[\/latex] and [latex]d[\/latex] is not a duplicate of an existing edge. Multigraph [latex]E[\/latex] is not an eulerization of [latex]A[\/latex] because vertices [latex]b[\/latex] and [latex]e[\/latex] have odd degree.<\/li>\n<li>Multigraph [latex]C[\/latex] uses [latex]3[\/latex] duplicate edges while multigraph [latex]D[\/latex] only uses [latex]2[\/latex]. So, [latex]D[\/latex] uses the fewest.<\/li>\n<li>Since there were four vertices in Graph [latex]A[\/latex], the fewest number of edges that could possibly eulerize the graph is half of four, which is two. So, it is not possible to eulerize Graph [latex]A[\/latex] using fewer edges.<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox proTip\">\n<p>It&#8217;s important to note that the process of eulerization should respect the rule that only existing edges can be duplicated; new edges cannot be created where there wasn&#8217;t one before.<\/p>\n<\/section>\n<p>The problem of finding the optimal eulerization is called the Chinese Postman Problem, a name given by an American in honor of the Chinese mathematician Mei-Ko Kwan who first studied the problem in 1962 while trying to find optimal delivery routes for postal carriers. \u00a0This problem is important in determining efficient routes for garbage trucks, school buses, parking meter checkers, street sweepers, and more.<\/p>\n","protected":false},"author":15,"menu_order":10,"template":"","meta":{"_candela_citation":"[{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Math in Society\",\"author\":\"David Lippman\",\"organization\":\"\",\"url\":\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"copyrighted_video\",\"description\":\"Graph Theory: Fleury\\'s Algorthim\",\"author\":\"James Sousa (Mathispower4u.com)\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/vvP4Fg4r-Ns\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"}]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"learn_it","content_attributions":null,"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1555"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":39,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1555\/revisions"}],"predecessor-version":[{"id":14839,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1555\/revisions\/14839"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/75"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1555\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=1555"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=1555"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=1555"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=1555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}