Graph TheoryⅡ Dog Can you find a path from each dog to each house such that no two paths intersect? A quadapus is a little-known animal similar to an octopus, but with four arms. Here are five quadapi resting on the seafloor Can each quadapus simultaneously shake hands with every other in such a way that no arms cross Informally, a planar graph is a graph that can be drawn in the plane so that no edges ross. Thus, these two puzzles are asking whether the graphs below are planar; that is whether they can be redrawn so that no edges cross In each case, the answer is, " No-but almost! "In fact, each drawing would be possible if le edge were removed More precisely, graph is planar if it has a planar embedding (or drawing ) This ly of associating each vertex with a distinct point in the plane and each edge with continuous, non-self-intersecting curve such that The endpoints of the curve associated with an edge(u, u)are the points associated with vertices u and uGraph Theory II 5 Dog Dog Dog Can you find a path from each dog to each house such that no two paths intersect? A quadapus is a little­known animal similar to an octopus, but with four arms. Here are five quadapi resting on the seafloor: Can each quadapus simultaneously shake hands with every other in such a way that no arms cross? Informally, a planar graph is a graph that can be drawn in the plane so that no edges cross. Thus, these two puzzles are asking whether the graphs below are planar; that is, whether they can be redrawn so that no edges cross. In each case, the answer is, “No— but almost!” In fact, each drawing would be possible if any single edge were removed. More precisely, graph is planar if it has a planar embedding (or drawing). This is a way of associating each vertex with a distinct point in the plane and each edge with a continuous, non­self­intersecting curve such that: • The endpoints of the curve associated with an edge (u, v) are the points associated with vertices u and v