CMPS345 Topic 11 Graph Lecture Notes PDF

Dr. Lama Affara Department of Mathematics and Computer Science Topics to be Covered – so far… Proof Recursion and Recurrence Counting Methods Induction Relation...

Dr. Lama Affara Department of Mathematics and Computer Science Topics to be Covered – so far… Proof Recursion and Recurrence Counting Methods Induction Relations Number Algorithms Graph Theory Cryptography Theory 12/15/2024 Discrete Structures II 2 http://strangemaps.files.wordpress.com/ 2007/02/fullinterstatemap-web.jpg Chemical Bonds http://4.bp.blogspot.com/-xCtBJ8lKHqA/Tjm0BONWBRI/AAAAAAAAAK4/-mHrbAUOHHg/s1600/ http://www.toothpastefordinner.com/ 12/15/2024 Discrete Structures II 7 What's in Common? Each of these structures consists of a collection of discrete objects Discrete links between those objects Goal: find a general framework for describing these objects, their relationships and properties. Today’s Outline Graphs What are Representing Graph Theory Graphs? Graphs Basic Graph Adjacency Lists Terminology Isomorphism Adjacency Graph Graph Models Matrices Connectivity Incidence Euler and Matrices Hamilton Paths Today’s Outline Graphs What are Representing Graph Theory Graphs? Graphs Basic Graph Adjacency Lists Terminology Isomorphism Adjacency Graph Graph Models Matrices Connectivity Incidence Euler and Matrices Hamilton Paths  A g r a p h is a structure for representing relationships. A graph consists of a set of v e r t i c e s (or nodes ) connected by e d g e s (or arcs)  A g r a p h is a structure for representing relationships. vertices A graph consists of a set of v e r t i c e s (or nodes ) connected by e d g e s (or arcs)  A g r a p h is a structure for representing relationships. edges A graph consists of a set of v e r t i c e s (or nodes ) connected by e d g e s (or arcs) Formalizing Graphs How might we define a graph mathematically? We need to specify what the vertices in the graph are, and which edges are in the graph The nodes can be pretty much anything. What about the edges? Vertex Definition Vertices can be anything Persons Cities Neurons Webpages Etc… Examples {Lama, Lea, Ayla, Nader} {Debbieh, Tripoli, Beirut} 12/15/2024 Discrete Structures II 17 Edge Definition Directed: Ordered pair of vertices. Represented as (u, v) directed from vertex u to v. u v Undirected: Unordered pair of vertices. Represented as {u, v}. Disregards any sense of direction and treats both end vertices interchangeably. u v  some graphs are directed 12/15/2024 Discrete Structures II 19  some graphs are undirected 12/15/2024 Discrete Structures II 20 Graph Definition Graph G =(V, E) where V is a set of vertices E is a set of edges Ordered pair ➔ Directed Graph (or digraph) Unordered pairs ➔ Undirected Graph ☞ “ G rap h ” m e a n s “ u n d ire c te d g ra p h ” ☜ Example – Definition - Directed 𝐺 =( {☺, ☺, ☺, , }, { ☺, ☺ , ☺, ☺ , ☺,  , ☺,  , ☺, ☺ , ☺,  , ☺,  , ☺,  , ☺,  , (, )}, )  Example – Definition - Undirected G =( {CAN, MAN, RAN, MAT, CAT, SAT, RAT}, { 𝐶𝐴𝑁, 𝑀𝐴𝑁 , {𝐶𝐴𝑁, 𝑅𝐴𝑁}, 𝑀𝐴𝑁, 𝑅𝐴𝑁 , 𝑀𝐴𝑇, 𝐶𝐴𝑇 , 𝑀𝐴𝑇, 𝑆𝐴𝑇 , 𝑀𝐴𝑇, 𝑅𝐴𝑇 , … }, ) Graph Terminology: Self-Loops An edge from a node to itself is called a self-loop. Represented as Undirected graph: edge {u, u} = {u} Directed graph: edge (u,u) Graph Terminology: Multiple Edge Multiple (Parallel Edges): Two or more edges joining the same pair of vertices. 𝐸 = 𝑒1 , 𝑒2 , 𝑒1 = 𝑢, 𝑣 , 𝑒2 = {𝑢, 𝑣} u v Graph Models Simple Graph Mixed Graph Multigraph Graph Models Directed Pseudograph multigraph Simple Directed Graph Graph Models: Simple Graph Undirected graph G=(V,E) consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called edges u v w Representation Example: G=(V, E), V = {u, v, w}, E = {{u, v}, {v, w}, {u, w}} Graph Models: Multigraph Undirected graph 𝐺 = (𝑉, 𝐸) consists of set of vertices 𝑉, set of Edges 𝐸 with multiple edges. When there are 𝑚 different edges associated to the same unordered pair of vertices {u, v}, we say that {u, v} is an edge of multiplicity 𝑚. u e1 e2 w e3 v Representation Example: G=(V, E), V = {u, v, w}, E = {e1, e2, e3} Graph Models: Pseudograph undirected graph G=(V,E) multiple edges and loops are allowed in such a graph u e1 e2 w e4 e3 v Representation Example: G=(V,E), V = {u, v, w}, E = {e1, e2, e3, e4} Graph Models: Simple Directed Graph Directed Graph or digraph G=(V, E) consists of V, a nonempty set of vertices, and E, a set of ordered pairs of distinct elements of V called edges u v w Representation Example: G(V, E), V = {u, v, w}, E = {(u, v), (v, w),(w, v),(w, u)} Graph Models: Directed Multigraph Directed Graph or digraph G=(V, E) consists of set of vertices V, set of Edges E with multiple edges. When there are 𝑚 different edges associated to the same ordered pair of vertices (u, v), we say that (u, v) is an edge of multiplicity 𝑚. u w e4 e1 e2 e3 v Representation Example: G=(V,E), V = {u, v, w}, E = {e1, e2, e3, e4} Here (u,v) has multiplicity 2 and (v,w) has multiplicity 1 Graph Models: Mixed Graph A graph with both directed and undirected edges is called a mixed graph u v w 12/15/2024 Discrete Structures II 33 Graph Models: Summary Graph Terminology: Adjacency Vertices u and v are adjacent if e={u, v} is an edge, e is called incident with u and v u and v are called endpoints of e u v Graph Terminology: Adjacency For the edge (u, v), u is adjacent to v OR v is adjacent from u u – Initial vertex, v – Terminal vertex u v Graph Terminology: Degree Degree of Vertex (deg (v)): the number of edges incident on a vertex. A loop contributes twice to the degree. deg(u)=1 u v deg(v)=3 Graph Terminology: Degree In-degree (deg- (u)): number of edges for which u is terminal vertex Out-degree (deg+ (u)): number of edges for which u is initial vertex deg- (v) = 1 deg- (u) = 0 u v deg+ (v) = 0 deg+ (u) = 1 Graph Terminology: Degree 𝐺 = {𝑉, 𝐸} where 𝑉 = {𝑢, 𝑣, 𝑤} , 𝐸 = { (𝑢, 𝑤), ( 𝑣, 𝑤), (𝑢, 𝑣), (𝑣, 𝑣) }, deg- (u) = 0, deg+ (u) = 2 deg- (v) = 2, deg+ (v) = 2 deg- (w) = 2, deg+ (w) = 0 u v w Graph Terminology: Degree deg−(a) = 2, deg−(b) = 2, deg−(c) = 3, deg−(d) = 2, deg−(e) = 3, deg−(f) = 0. deg+(a) = 4, deg+(b) = 1, deg+(c) = 2, deg+(d) = 2, deg+ (e) = 3, deg+(f) = 0. Graph Terminology: Neighborhood The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called the neighborhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. Degrees and Neighborhoods of Vertices What are the degrees and neighborhoods of the vertices in the following graph? deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) = 3, deg(g) = 0. N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c}, N(e) = {b, c , f }, N(f) = {a, b, c, e}, N(g) = . Degrees and Neighborhoods of Vertices What are the degrees and neighborhoods of the vertices in the following graph? deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5. N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b}, N(d) = {a, b, e}, N(e) = {a, b ,d}. Graph Terminology: Pendant and Isolated Pendant Vertex: deg (u) =1 (adjacent to exactly one other vertex) u v t Isolated Vertex: deg (v) = 0 (not adjacent to any vertex) u Graph Terminology: Pendant and Isolated 𝐺 = {𝑉, 𝐸} where 𝑉 = {𝑢, 𝑣, 𝑤, 𝑘} , 𝐸 = { {𝑢, 𝑤}, {𝑢, 𝑣}, {𝑤, 𝑤}} deg (u) = 2, deg (v) = 1, deg (w) = 3, deg (k) = 0, v is pendant k is isolated u v k w Graph Theorem 1: Handshaking Theorem If G = (V,E) is an undirected graph with m edges, then 2𝑚 = ෍ deg(𝑣) 𝑣∈𝑉 Proof: Each edge contributes twice to the degree count of all vertices. Hence, both the left-hand and right-hand sides of this equation equal twice the number of edges. Think about the graph where vertices represent the people at a party and an edge connects two people who have shaken hands. Graph Theorem 1: Handshaking Theorem Example: How many edges are there in a graph with 10 vertices each of degree six? Solution: Because the sum of the degrees of the vertices is 6  10 = 60, the handshaking theorem tells us that 2m = 60. So the number of edges m = 30. i.e. if there is a room with 10 people and each person handshakes hands with six people, there are a 30 connections made Graph Theorem 1: Handshaking Theorem Example: If a graph has 5 vertices, can each vertex have degree 3? Solution: This is not possible by the handshaking thorem! Why? because the sum of the degrees of the vertices 3  5 = 15 is odd. So no such graph exists!  Six Degrees of Separation or Six Handshakes Rule https://www.youtube.com/watch?v=a99ry70CnRs https://www.youtube.com/watch?v=TcxZSmzPw8k 12/15/2024 Discrete Structures II 49 Graph Theorem 2 An undirected graph has an even number of vertices of odd degree. Proof: Let V1 be the vertices of even degree and V2 be the vertices of odd degree in an undirected graph G = (V, E) with m edges. Then even This sum must be even because 2m is must be even even and the sum of the degrees of since deg(v) the vertices of even degrees is also is even for even. Because this is the sum of the each v ∈ V1 degrees of all vertices of odd degree in the graph, there must be an even number of such vertices. Graph Theorem 3 Theorem 3: Let G = (V, E) be a graph with directed edges. Then: Proof: The first sum counts the number of outgoing edges over all vertices and the second sum counts the number of incoming edges over all vertices. It follows that both sums equal the number of edges in the graph. Today’s Outline Graphs What are Representing Graph Theory Graphs? Graphs Basic Graph Adjacency Lists Terminology Isomorphism Adjacency Graph Graph Models Matrices Connectivity Incidence Euler and Matrices Hamilton Paths Representing Graphs: Adjacency Lists Definition: An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph. Representing Graphs: Adjacency Lists Definition: An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph. Representation- Adjacency List Each node (vertex) has a list of which node Adjacency List nodes (vertex) it is adjacent Example: undirectd graph G (V, E) u v,w u v w, u w u,v v w Representing Graphs: Adjacency Lists 12/15/2024 Discrete Structures II 56 Representing Graphs: Adjacency Matrices Definition: Suppose that G = (V, E) is a simple graph where |V| = n. Arbitrarily list the vertices of G as 𝑣1 , 𝑣2 , … , 𝑣𝑛. The adjacency matrix 𝐴𝐺 of 𝐺 𝑛 × 𝑛 zero-one matrix 𝑖, 𝑗 𝑡ℎ entry for 𝑣𝑖 and 𝑣𝑗 1 when adjacent 0 when not adjacent. If the graphs adjacency matrix is 𝐴𝐺 = [𝑎𝑖𝑗 ], then Representation- Adjacency Matrix Example: Undirected Graph G (V,E) v u w v 0 1 1 u u 1 0 1 w 1 1 0 v w Representation- Adjacency Matrix Example: directed Graph G (V, E ) v u w v 0 1 0 u u 0 0 1 w 1 0 0 v w Representing Graphs: Adjacency Matrices a b c d a b c d The adjacency matrix of a simple graph is symmetric, i.e., aij = aji a b c d Also, since there are no a b c d loops, each diagonal entry aij =0 for i = 1, 2, 3, …, n Representing Graphs: Adjacency Matrices Adjacency matrices can also be used to represent graphs with loops and multiple edges. A loop at the vertex 𝑣𝑖 is represented by a 1 at the 𝑖, 𝑖 𝑡ℎ position of the matrix. When multiple edges connect the same pair of vertices 𝑣𝑖 and 𝑣𝑗 , (or if multiple loops are present at the same vertex), the 𝑖, 𝑗 𝑡ℎ entry equals the number of edges connecting the pair of vertices. a b c d a b c d Representation- Adjacency Matrix/List 62 Representing Graphs: Incidence Matrices Definition: Let G = (V, E) be an undirected graph with vertices where v1, v2, … vn and edges e1, e2, … em. The incidence matrix with respect to the ordering of V and E is 𝑛 × 𝑚 matrix 𝑀 = [𝑚𝑖𝑗 ], where Representing Graphs: Incidence Matrices 𝑒1 𝑒2 𝑒3 𝑒4 𝑒5 𝑒6 𝑒1 𝑒2 𝑒3 𝑒4 𝑒5 𝑒6 𝑒7 𝑒8 Representing Graphs Incidence (Matrix): Most useful when information about edges is more desirable than information about vertices. Adjacency (Matrix/List): Most useful when information about the vertices is more desirable than information about the edges. These representations are most popular since information about the vertices is often more desirable than edges in most applications Representing Graphs When a graph is sparse: has few edges relatively to the total number of possible edges ➔ it is much more efficient to represent the graph using an adjacency list than an adjacency matrix. But for a dense graph, which includes a high percentage of possible edges, ➔ an adjacency matrix is preferable. 12/15/2024 Discrete Structures II 66 Today’s Outline Graphs What are Representing Graph Theory Graphs? Graphs Basic Graph Adjacency Lists Terminology Isomorphism Adjacency Graph Graph Models Matrices Connectivity Incidence Euler and Matrices Hamilton Paths Graph Isomorphism How many graphs exist with n vertices where the vertices are labeled? 1 vertex u 2 vertices u v u v w w w w w w w w 3 vertices u v u v u v u v u v u v u v u v What if we take away the labels? 12/15/2024 Discrete Structures II 68 Isomorphism of Graphs 𝐺1 = (𝑉1 , 𝐸1 ) and 𝐺2 = (𝑉2 , 𝐸2 ) are isomorphic if there is a one-to-one and onto (bijective) function 𝑓 from 𝑉1 to 𝑉2 with the property that for all a and b in 𝑉1 a and b are adjacent in 𝐺1 𝑓(𝑎) and 𝑓(𝑏) are adjacent in 𝐺2 Function 𝑓 is called an isomorphism.  Another Example (Isomorphism) This graph is isomorphic to … 12/15/2024 Discrete Structures II 70 Applications of Graph Isomorphism chemists use molecular graphs to model chemical compounds. Vertices represent atoms and edges represent chemical bonds. When a new compound is synthesized, a database of molecular graphs is checked to determine whether the graph representing the new compound is isomorphic to the graph of a compound that is already known. Applications of Graph Isomorphism Electronic circuits are modeled as graphs in which the vertices represent components and the edges represent connections between them. verification that a particular layout of a circuit corresponds to the design’s original schematics. determining whether a chip from one vendor includes the intellectual property of another vendor. Graph - Isomorphism 𝐺1 = (𝑉1 , 𝐸1 ) , 𝐺2 = (𝑉2 , 𝐸2 ) Same |V|, same |E|, similar degrees for all vertices ➔ Isomorphic: f (u1) = v1, f (u2) = v4, f (u3) = v3, f (u4) = v2 u1 u2 v1 v2 u3 u4 v4 v3 Graph - Isomorphism 𝐺1 = (𝑉1 , 𝐸1 ) , 𝐺2 = (𝑉2 , 𝐸2 ) Same |V|, same |E|, deg(𝑣3 )=3 (no matching degree in 𝐺1 ) ➔ Not isomorphic u1 u2 v1 v2 u3 u4 v4 v3 Isomorphism of Graphs (cont.) It is difficult to determine whether two simple graphs are isomorphic using brute force because there are n! possible one-to-one correspondences between the vertex sets of two simple graphs with n vertices. The best algorithms for determining weather two graphs are isomorphic have exponential worst case complexity in terms of the number of vertices of the graphs. Isomorphism of Graphs (cont.) Sometimes it is not hard to show that two graphs are not isomorphic find a property, preserved by isomorphism, that only one of the two graphs has ➔ graph invariant Graph Invariants A graph invariant is a property, (usually a number), that is preserved under an isomorphism. Some graph invariants are: |V(G)| = number of vertices |E(G)| = number of edges d(G) = minimal degree. D(G) = maximal degree. Invariants - Example a 1 2 |V(G)| = 4 c b |E(G)| = 5 d d(G) = 2 e D(G) = 3 3 4 Isomorphism of Graphs (cont.) Example: Determine whether these two graphs are isomorphic. Solution: Both graphs have eight vertices and ten edges. They also both have four vertices of degree two and four of degree three. However, G and H are not isomorphic. Note that since deg(a) = 2 in G, a must correspond to t, u, x, or y in H, because these are the vertices of degree 2. But each of these vertices is adjacent to another vertex of degree two in H, which is not true for a in G. Alternatively, note that the subgraphs of G and H made up of vertices of degree three and the edges connecting them must be isomorphic. But these subgraphs, are not isomorphic. Isomorphism of Graphs (cont.) Example: Determine whether these two graphs are isomorphic. Solution: Both graphs have six vertices and seven edges. They also both have four vertices of degree two and two of degree three. The subgraphs of G and H consisting of all the vertices of degree two and the edges connecting them are isomorphic. So, it is reasonable to try to find an isomorphism f. We define an injection f from the vertices of G to the vertices of H that preserves the degree of vertices. We will determine whether it is an isomorphism. The function f with f(u1) = v6, f(u2) = v3, f(u3) = v4, and f(u4) = v5 , f(u5) = v1, and f(u6) = v2 is a one-to-one correspondence between G and H. Showing that this correspondence preserves edges is straightforward, so we will omit the details here. Because f is an isomorphism, it follows that G and H are isomorphic graphs. Algorithms for Graph Isomorphism The best algorithms known for determining whether two graphs are isomorphic have exponential worst-case time complexity (in the number of vertices of the graphs). However, there are algorithms with linear average-case time complexity. You can use a public domain program called NAUTY to determine in less than a second whether two graphs with as many as 100 vertices are isomoprhic. Today’s Outline Graphs What are Representing Graph Theory Graphs? Graphs Basic Graph Adjacency Lists Terminology Isomorphism Adjacency Graph Graph Models Matrices Connectivity Incidence Euler and Matrices Hamilton Paths Determine if a message can be sent between two computers on a network. Represent the network as a graph Check if a path along the edges exist from the source computer to the destination 12/15/2024 Discrete Structures II 83 Connectivity Basic Idea: the graph reachability among vertices by traversing the edges. Application Examples: In a city-to-city road-network, if one city can be reached from another city. Problems of determining whether a message can be sent between two computers using intermediate links. Efficiently planning routes for data delivery on the Internet.  How to represent a path mathematically? 12/15/2024 Discrete Structures II 85 Path A Path (walk) is a sequence of edges that begins at a vertex of a graph and travels along edges of the graph, always connecting pairs of adjacent vertices. Representation: G = (V, E), Path P represented, from u to v is of length 4 and can be written as: ((u, 1), (1, 4), (4, 5), (5, v)). For Simple Graphs, the path can be denoted only by the sequence (u,1,4,5,v) 2 1 v 3 u 4 5 Path Terminology The path is a circuit (closed walk) if it begins and ends at the same vertex (u = v) and has length greater than zero. The path or circuit is said to pass through the vertices and traverse the edges A path or circuit is a simple path (trail) if it does not contain the same edge more than once. 12/15/2024 Discrete Structures II 87 Path Example: In the simple graph here (a, d, c, f, e) is a simple path of length 4. (d, e, c, a) is not a path because e is not connected to c. (b, c, f, e, b) is a circuit of length 4. (a, b, e, d, a, b) is a path of length 5, but it is not a simple path Connectedness An undirected graph is connected if there exists a path between every pair of distinct vertices in the graph. v4 v1 v3 v2 v5 G (V, E) is connected since for V = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 }, there exists a path between {𝑣𝑖 , 𝑣𝑗 }, 1 ≤ 𝑖, 𝑗 ≤ 5, 𝑖  𝑗 Connectedness connected Not connected 12/15/2024 Discrete Structures II 90 Connectedness Theorem There is a simple path between every pair of distinct vertices of a connected undirected graph. Connected Components The graph that is not connected is the union of two or more connected graphs. This disjoint connected subgraphs are called the connected components of the graph. 12/15/2024 Discrete Structures II 92 Today’s Outline Graphs What are Representing Graph Theory Graphs? Graphs Basic Graph Adjacency Lists Terminology Isomorphism Adjacency Graph Graph Models Matrices Connectivity Incidence Euler and Matrices Hamilton Paths The Seven Bridges of Königsberg, Russia The residents of Königsberg, Russia, wondered if it was possible to take a walking tour of the town that crossed each of the seven bridges over the Pregel river exactly once. Is it possible to start at some node and take a walk that uses each edge exactly once, and end at the starting node? The Seven Bridges of Königsberg, Russia The Seven Bridges of Königsberg, Russia The Seven Bridges of Königsberg, Russia C A D B The Seven Bridges of Königsberg, Russia C A D B The Seven Bridges of Königsberg, Russia The Swiss mathematician C Leonard Euler proved that no such path exists. A D (Even if we allow the walk to start and finish in different places.) B This result is often considered to be the first theorem ever proved in graph theory. The Seven Bridges of Königsberg, Russia Is it possible to start at some node and take a walk that uses each edge exactly once, and end at the starting node? Is there a simple circuit in this multigraph that contains every edge? Remember: a simple circuit is a circuit that uses each edge once 12/15/2024 Discrete Structures II 100 Euler Path Euler path (Euler trail, Euler walk): uses each edge precisely once. If such a path exists, the graph is called traversable. Euler Circuit Euler circuit (Euler cycle, Euler tour): a cycle that uses each edge precisely once. If such a cycle exists, the graph is called Eulerian (also unicursal). Euler Path and Circuit Which of the undirected graphs has a Euler circuit? Of those that do not, which has an Euler path? Euler circuit none Euler path (a, e, c, d, e, b, a) (a, c, d, e, b, d, a, b) 12/15/2024 Discrete Structures II 103  Is there a quick and easy way to use the degrees of each vertex to identify graphs that do or don't have Euler paths? 12/15/2024 Discrete Structures II 104 Euler Path Yes 4 2 2 No 4 0 4 No 5 1 4 Yes 4 2 2 Yes 5 3 2 Yes 5 3 2 Yes 6 4 2 12/15/2024 Discrete Structures II 105 Euler Path The number of vertices of odd degree must be either zero or two. If not then there is no "Euler Path" And if there are two vertices with odd degree, then they are the starting and ending vertices. Why? A path leads into a vertex by one edge and out by a second edge. So the edges should come in pairs (an even number). Only the start and end point can have an odd degree. 12/15/2024 Discrete Structures II 106 Euler Theorems 1. A connected graph G is Eulerian (Euler Circuit) iff G is connected has no vertices of odd degree. 2. A connected graph G has an Euler trail and not an Euler circuit from node a to some other node b iff G is connected a  b are the only two nodes of odd degree The Seven Bridges of Königsberg, Russia C Vertices C, B and D have degree 3 and vertex A has degree 5, so this graph has four vertices of odd A D degree. So it does not have an Euler Path. B Euler Circuits and Paths G1 contains exactly two vertices of odd degree (b and d). Hence it has an Euler path, e.g., d, a, b, c, d, b. G2 has exactly two vertices of odd degree (b and d). Hence it has an Euler path, e.g., b, a, g, f, e, d, c, g, b, c, f, d. G3 has six vertices of odd degree. Hence, it does not have an Euler path. Applications of Euler Paths and Circuits Euler paths and circuits can be used to solve many practical problems such as finding a path or circuit that traverses each street in a neighborhood, road in a transportation network, connection in a utility grid, link in a communications network. Other applications are found in the layout of circuits, network multicasting, molecular biology, where Euler paths are used in the sequencing of DNA. Hamiltonian Path and Circuit Hamiltonian path (traceable path): a path that visits each vertex exactly once. ➔ Traceable graph Hamiltonian Path and Circuit Hamiltonian cycle (traceable path): a cycle that visits each vertex exactly once. except for the starting vertex, which is visited once at the start and once again at the end ➔ Hamiltonian Graph Hamiltonian Path and Circuit A graph of the vertices of a dodecahedron. Is it Hamiltonian? Hamiltonian Path and Circuit This graph has a Hamiltonian path, but not a Hamiltonian cycle. Hamiltonian Path and Circuit This graph has an Euler path and cycle, but no Hamiltonian cycle. It also has a Hamiltonian path.