{"id":1503,"date":"2023-04-10T16:28:20","date_gmt":"2023-04-10T16:28:20","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=1503"},"modified":"2024-10-18T20:58:06","modified_gmt":"2024-10-18T20:58:06","slug":"graph-theory-basics-learn-it-1","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/graph-theory-basics-learn-it-1\/","title":{"raw":"Graph Theory Basics: Learn It 1","rendered":"Graph Theory Basics: Learn It 1"},"content":{"raw":"<section class=\"textbox learningGoals\">\r\n<ul>\r\n\t<li>Recognize graph components: vertices, edges, loops, and vertex degrees<\/li>\r\n\t<li>Identify both a path and a circuit through a graph<\/li>\r\n\t<li>Determine whether a graph is connected or disconnected<\/li>\r\n\t<li>Find the shortest path through a graph using Dijkstra's Algorithm<\/li>\r\n<\/ul>\r\n<\/section>\r\n<h2>Drawing Graphs<\/h2>\r\n<p>In the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for high-speed internet, and suggesting new friends within social network websites like Facebook. Let's look at an example of planning an effective route.<\/p>\r\n<section class=\"textbox example\">Here is a portion of a housing development from Missoula, Montana. As part of her job, the development\u2019s lawn inspector has to walk down every street in the development making sure homeowners\u2019 landscaping conforms to the community requirements.<center><img class=\"alignnone wp-image-134 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155110\/Fig2_5_1.png\" alt=\"A map of the streets and houses in the development\" width=\"574\" height=\"438\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nNaturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.<center><img class=\"aligncenter wp-image-135 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"A graph made from a map of streets by drawing an edge where each street is and a vertex where every intersection is.\" width=\"700\" height=\"264\" \/><\/center><\/section>\r\n<p>This type of simplified picture is called a <strong>graph<\/strong>.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Graphs, vertices, and edges<\/h3>\r\n<p>A <strong>graph<\/strong> consists of a set of dots, called <strong>vertices<\/strong>, and a set of <strong>edges<\/strong> connecting pairs of vertices.<\/p>\r\n<\/div>\r\n<\/section>\r\n<p>You probably already noticed that we are using the term<em> graph<\/em> differently than you may have used the term in the past to describe the graph of a mathematical function.<\/p>\r\n<p>While we loosely defined some terminology earlier, we now will try to be more specific.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Parts of a graph<\/h3>\r\n<h4>vertex<\/h4>\r\n<p>A <strong>vertex<\/strong> is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like \u201cwork\u201d or \u201cschool\u201d. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass\u2014the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.<\/p>\r\n<h4>edges<\/h4>\r\n<p><strong>Edges<\/strong> connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight. It is not necessary for the edges in a graph to be straight. In fact, you can draw an edge any way you want.<\/p>\r\n<h4>loop<\/h4>\r\n<p>A<strong> loop<\/strong> is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.<\/p>\r\n<p>&nbsp;<\/p>\r\n<center><img class=\"alignnone wp-image-140\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155118\/Fig2_5_7.png\" alt=\"Three vertices connected to each other by edges. One vertex has a loop connecting itself to itself.\" width=\"245\" height=\"147\" \/><\/center>\r\n<h4>degree of a vertex<\/h4>\r\n<p>The <strong>degree of a vertex<\/strong> is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.<\/p>\r\n<p>&nbsp;<\/p>\r\n<center>\r\n<table>\r\n<thead>\r\n<tr>\r\n<th>Degree [latex]0[\/latex]<\/th>\r\n<th>Degree [latex]1[\/latex]<\/th>\r\n<th>Degree [latex]2[\/latex]<\/th>\r\n<th>Degree [latex]3[\/latex]<\/th>\r\n<th>Degree [latex]4[\/latex]<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td><img class=\"alignnone wp-image-141\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_8.png\" alt=\"A dot.\" width=\"30\" height=\"30\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-142\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_9.png\" alt=\"A dot with one line attached to it.\" width=\"90\" height=\"46\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-143\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_10.png\" alt=\"A dot with two lines attached to it.\" width=\"140\" height=\"57\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-144\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_11.png\" alt=\"A dot with three lines attached to it.\" width=\"140\" height=\"93\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-145\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155121\/Fig2_5_12.png\" alt=\"A dot with four lines attached to it.\" width=\"140\" height=\"96\" \/><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/center>\r\n<h4>path<\/h4>\r\n<p>A <strong>path<\/strong> is a sequence of vertices such that each vertex is adjacent to the next one. In a path, no vertex is repeated. For example, a path from vertex [latex]A[\/latex] to vertex [latex]M[\/latex] is shown below. It is one of many possible paths in this graph.<\/p>\r\n<p>&nbsp;<\/p>\r\n<center><img class=\"alignnone wp-image-146\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155122\/Fig2_5_13.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A path is drawn from A to M going though the points B, F, G, and H.\" width=\"350\" height=\"148\" \/><\/center>\r\n<h4>circuit<\/h4>\r\n<p>A <strong>circuit<\/strong> is a path that begins and ends at the same vertex. A circuit starting and ending at vertex [latex]A[\/latex] is shown below.<\/p>\r\n<p>&nbsp;<\/p>\r\n<center><img class=\"alignnone wp-image-147\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155123\/Fig2_5_14.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A circuit is drawn, going through the points A, B, F, G, L, L, J, and E.\" width=\"350\" height=\"150\" \/><\/center>\r\n<h4>connected graphs<\/h4>\r\n<p>A graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is <strong>disconnected<\/strong>; there is no way to get from the vertices on the left to the vertices on the right.<\/p>\r\n<p>&nbsp;<\/p>\r\n<center><img class=\"alignnone wp-image-148\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155124\/Fig2_5_15.png\" alt=\"A 3x4 graph where there is not a path from every vertex to every other vertex.\" width=\"350\" height=\"137\" \/><\/center>\r\n<h4>weights<\/h4>\r\n<p>Depending upon the problem being solved, sometimes weights are assigned to the edges. The <strong>weights<\/strong> could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.<\/p>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox proTip\">\r\n<p>Not every list of vertices or list of edges makes a path. The order must take into account the way in which the edges and vertices are connected. The list must be a sequence, which means they are in order. No edges or vertices can be skipped and you cannot go off the graph.<\/p>\r\n<\/section>\r\n<section class=\"textbox example\">The graph below shows [latex]5[\/latex] cities. The weights on the edges represent the airfare for a one -way flight between the cities.\r\n\r\n<p style=\"padding-left: 30px;\">a. How many vertices and edges does the graph have?<br \/>\r\nb. Is the graph connected?<br \/>\r\nc. What is the degree of the vertex representing LA?<br \/>\r\nd. If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?<br \/>\r\ne. If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit.<\/p>\r\n<center><img class=\"aligncenter size-full wp-image-11949\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/29184337\/Screen-Shot-2017-01-23-at-6.02.20-PM.png\" alt=\"Five dots labeled Seattle, LA, Chicago, Atlanta, and Dallas respectively. Every dot is connected directly to every other dot\" width=\"331\" height=\"166\" \/><\/center>\r\n<p>[reveal-answer q=\"942356\"]Show Solution[\/reveal-answer]<br \/>\r\n[hidden-answer a=\"942356\"]<\/p>\r\n<p>a. [latex]5[\/latex] vertices, [latex]10[\/latex] edges<\/p>\r\n<p>b. yes<\/p>\r\n<p>c. [latex]4[\/latex]<\/p>\r\n<p>d. path<\/p>\r\n<p>e. circuit<\/p>\r\n<p>[\/hidden-answer]<\/p>\r\n<\/section>\r\n<section class=\"textbox proTip\">\r\n<p>When listing the vertices and edges in a graph, work in alphabetical order to avoid accidentally listing the same item twice. When you are finished, count the number of vertices or edges you listed and compare that to the number of vertices or edges on the graph to ensure you didn\u2019t miss any.<\/p>\r\n<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]6899[\/ohm2_question]<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]6900[\/ohm2_question]<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]12707[\/ohm2_question]<\/section>","rendered":"<section class=\"textbox learningGoals\">\n<ul>\n<li>Recognize graph components: vertices, edges, loops, and vertex degrees<\/li>\n<li>Identify both a path and a circuit through a graph<\/li>\n<li>Determine whether a graph is connected or disconnected<\/li>\n<li>Find the shortest path through a graph using Dijkstra&#8217;s Algorithm<\/li>\n<\/ul>\n<\/section>\n<h2>Drawing Graphs<\/h2>\n<p>In the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for high-speed internet, and suggesting new friends within social network websites like Facebook. Let&#8217;s look at an example of planning an effective route.<\/p>\n<section class=\"textbox example\">Here is a portion of a housing development from Missoula, Montana. As part of her job, the development\u2019s lawn inspector has to walk down every street in the development making sure homeowners\u2019 landscaping conforms to the community requirements.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-134 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155110\/Fig2_5_1.png\" alt=\"A map of the streets and houses in the development\" width=\"574\" height=\"438\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-135 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"A graph made from a map of streets by drawing an edge where each street is and a vertex where every intersection is.\" width=\"700\" height=\"264\" \/><\/div>\n<\/section>\n<p>This type of simplified picture is called a <strong>graph<\/strong>.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>Graphs, vertices, and edges<\/h3>\n<p>A <strong>graph<\/strong> consists of a set of dots, called <strong>vertices<\/strong>, and a set of <strong>edges<\/strong> connecting pairs of vertices.<\/p>\n<\/div>\n<\/section>\n<p>You probably already noticed that we are using the term<em> graph<\/em> differently than you may have used the term in the past to describe the graph of a mathematical function.<\/p>\n<p>While we loosely defined some terminology earlier, we now will try to be more specific.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>Parts of a graph<\/h3>\n<h4>vertex<\/h4>\n<p>A <strong>vertex<\/strong> is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like \u201cwork\u201d or \u201cschool\u201d. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass\u2014the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.<\/p>\n<h4>edges<\/h4>\n<p><strong>Edges<\/strong> connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight. It is not necessary for the edges in a graph to be straight. In fact, you can draw an edge any way you want.<\/p>\n<h4>loop<\/h4>\n<p>A<strong> loop<\/strong> is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-140\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155118\/Fig2_5_7.png\" alt=\"Three vertices connected to each other by edges. One vertex has a loop connecting itself to itself.\" width=\"245\" height=\"147\" \/><\/div>\n<h4>degree of a vertex<\/h4>\n<p>The <strong>degree of a vertex<\/strong> is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\">\n<table>\n<thead>\n<tr>\n<th>Degree [latex]0[\/latex]<\/th>\n<th>Degree [latex]1[\/latex]<\/th>\n<th>Degree [latex]2[\/latex]<\/th>\n<th>Degree [latex]3[\/latex]<\/th>\n<th>Degree [latex]4[\/latex]<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-141\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_8.png\" alt=\"A dot.\" width=\"30\" height=\"30\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-142\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_9.png\" alt=\"A dot with one line attached to it.\" width=\"90\" height=\"46\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-143\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_10.png\" alt=\"A dot with two lines attached to it.\" width=\"140\" height=\"57\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-144\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_11.png\" alt=\"A dot with three lines attached to it.\" width=\"140\" height=\"93\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-145\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155121\/Fig2_5_12.png\" alt=\"A dot with four lines attached to it.\" width=\"140\" height=\"96\" \/><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<h4>path<\/h4>\n<p>A <strong>path<\/strong> is a sequence of vertices such that each vertex is adjacent to the next one. In a path, no vertex is repeated. For example, a path from vertex [latex]A[\/latex] to vertex [latex]M[\/latex] is shown below. It is one of many possible paths in this graph.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-146\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155122\/Fig2_5_13.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A path is drawn from A to M going though the points B, F, G, and H.\" width=\"350\" height=\"148\" \/><\/div>\n<h4>circuit<\/h4>\n<p>A <strong>circuit<\/strong> is a path that begins and ends at the same vertex. A circuit starting and ending at vertex [latex]A[\/latex] is shown below.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-147\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155123\/Fig2_5_14.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A circuit is drawn, going through the points A, B, F, G, L, L, J, and E.\" width=\"350\" height=\"150\" \/><\/div>\n<h4>connected graphs<\/h4>\n<p>A graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is <strong>disconnected<\/strong>; there is no way to get from the vertices on the left to the vertices on the right.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-148\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155124\/Fig2_5_15.png\" alt=\"A 3x4 graph where there is not a path from every vertex to every other vertex.\" width=\"350\" height=\"137\" \/><\/div>\n<h4>weights<\/h4>\n<p>Depending upon the problem being solved, sometimes weights are assigned to the edges. The <strong>weights<\/strong> could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.<\/p>\n<\/div>\n<\/section>\n<section class=\"textbox proTip\">\n<p>Not every list of vertices or list of edges makes a path. The order must take into account the way in which the edges and vertices are connected. The list must be a sequence, which means they are in order. No edges or vertices can be skipped and you cannot go off the graph.<\/p>\n<\/section>\n<section class=\"textbox example\">The graph below shows [latex]5[\/latex] cities. The weights on the edges represent the airfare for a one -way flight between the cities.<\/p>\n<p style=\"padding-left: 30px;\">a. How many vertices and edges does the graph have?<br \/>\nb. Is the graph connected?<br \/>\nc. What is the degree of the vertex representing LA?<br \/>\nd. If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?<br \/>\ne. If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-11949\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/29184337\/Screen-Shot-2017-01-23-at-6.02.20-PM.png\" alt=\"Five dots labeled Seattle, LA, Chicago, Atlanta, and Dallas respectively. Every dot is connected directly to every other dot\" width=\"331\" height=\"166\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/29184337\/Screen-Shot-2017-01-23-at-6.02.20-PM.png 331w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/29184337\/Screen-Shot-2017-01-23-at-6.02.20-PM-300x150.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/29184337\/Screen-Shot-2017-01-23-at-6.02.20-PM-65x33.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/29184337\/Screen-Shot-2017-01-23-at-6.02.20-PM-225x113.png 225w\" sizes=\"(max-width: 331px) 100vw, 331px\" \/><\/div>\n<p><div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q942356\">Show Solution<\/button><\/p>\n<div id=\"q942356\" class=\"hidden-answer\" style=\"display: none\">\n<p>a. [latex]5[\/latex] vertices, [latex]10[\/latex] edges<\/p>\n<p>b. yes<\/p>\n<p>c. [latex]4[\/latex]<\/p>\n<p>d. path<\/p>\n<p>e. circuit<\/p>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox proTip\">\n<p>When listing the vertices and edges in a graph, work in alphabetical order to avoid accidentally listing the same item twice. When you are finished, count the number of vertices or edges you listed and compare that to the number of vertices or edges on the graph to ensure you didn\u2019t miss any.<\/p>\n<\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm6899\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=6899&theme=lumen&iframe_resize_id=ohm6899&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm6900\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=6900&theme=lumen&iframe_resize_id=ohm6900&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm12707\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=12707&theme=lumen&iframe_resize_id=ohm12707&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n","protected":false},"author":15,"menu_order":4,"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\":\"cc\",\"description\":\"Pleasant View housing development\",\"author\":\"Sam Beebe\",\"organization\":\"\",\"url\":\"https:\/\/flic.kr\/p\/5kTroZ\",\"project\":\"\",\"license\":\"cc-by\",\"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":[{"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":"cc","description":"Pleasant View housing development","author":"Sam Beebe","organization":"","url":"https:\/\/flic.kr\/p\/5kTroZ","project":"","license":"cc-by","license_terms":""}],"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\/1503"}],"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":31,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1503\/revisions"}],"predecessor-version":[{"id":12005,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1503\/revisions\/12005"}],"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\/1503\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=1503"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=1503"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=1503"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=1503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}