Graph Theory Lesson 1 PDF

Chapter 1: Graphs and Subgraphs Rafael A. Duarte Department of Mathematics and Statistics Math 20223 Graph Theory with Application Thursday 14th November, 2024  History What is Graph...

Chapter 1: Graphs and Subgraphs Rafael A. Duarte Department of Mathematics and Statistics Math 20223 Graph Theory with Application Thursday 14th November, 2024  History What is Graph 1/56 History Konigsberg Problem Kaliningrad Russia 18th Century Leonard Euler Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 2/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 3/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 4/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 5/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 6/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 7/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 8/56 What is Graph a join u and v. b join u to itself. e join v and x. Exercise. Check all other edges joining two vertices. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 9/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 10/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 11/56 What is Graph u and v are ends of a. u is an end of b. v and x are ends of e. Exercise. List down the ends of all the remaining other edges. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 12/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 13/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 14/56 What is Graph u is adjacent v or u ∼ v. u ∼ u. v ∼ x. Exercise. List down all other adjacent vertices. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 15/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 16/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 17/56 What is Graph w is incident to a. x is incident to a. u is incident to a. Exercise. List down all other vertices that are incident to an edge. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 18/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 19/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 20/56 What is Graph b is a loop. All edges except b are links. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 21/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 22/56 What is Graph Consider the graph G below Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 23/56 What is Graph Consider the graph G below ν(G) = 5 ε(G) = 8 Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 24/56 What is Graph Consider the graph H below Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 25/56 What is Graph Consider the graph H below ν(G) = 5 ε(G) = 8 Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 26/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 27/56 What is Graph Consider the graph G below What is the neighborhood of v2 and v3. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 28/56 What is Graph Consider the graph G below N(v2 ) := {v5 , v4 } N(v3 ) := {v2 , v3 , v4 } Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 29/56 What is Graph Consider the graph H below What is the neighborhood of u and x. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 30/56 What is Graph Consider the graph H below N(u) := {u, v, x} N(x) := {v, w, u, y} Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 31/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 32/56 What is Graph Consider the graph G below What is the degree of v2 and v3. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 33/56 What is Graph Consider the graph G below Since N(v2 ) := {v5 , v4 }, then deg(v2 ) = 2. Since N(v3 ) := {v2 , v3 , v4 }, then deg(v3 ) = 3. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 34/56 What is Graph Consider the graph H below What is the degree of u and x. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 35/56 What is Graph Consider the graph H below Since N(u) := {u, v, x}, then deg(u) = 3. Since N(x) := {v, w, u, y}, then deg(u) = 4. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 36/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 37/56 What is Graph Consider the graph G below Question: What vertex is a dominating vertex? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 38/56 What is Graph Consider the graph G below Question: What vertex is a dominating vertex? Answer: v2 is the only dominating vertex of G. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 39/56 What is Graph Consider the graph H below Question: What vertex is a dominating vertex? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 40/56 What is Graph Consider the graph H below Question: What vertex is a dominating vertex? Answer: x is the only dominating vertex of G. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 41/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 42/56 What is Graph Consider the graph X below Question: What is the isolated vertex of the graph X? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 43/56 What is Graph Consider the graph X below Question: What is the isolated vertex of the graph X? Answer: v is the only isolated vertex of X. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 44/56 What is Graph Consider the graph Y below Question: What is the isolated vertices of the graph Y? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 45/56 What is Graph Consider the graph Y below Question: What is the isolated vertices of the graph Y? Answer: r and s are the isolated vertices of Y. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 46/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 47/56 What is Graph Consider the graph G below Question: What is the maximum and minumum degree of G? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 48/56 What is Graph Consider the graph G below Question: What is the maximum and minumum degree of G? Solution: N(v1 ) := {v2 } =⇒ deg(v1 ) = 1. N(v2 ) := {v1 , v3 , v4 , v5 } =⇒ deg(v2 ) = 4. N(v3 ) := {v2 , v3 , v4 } =⇒ deg(v3 ) = 3. N(v4 ) := {v2 , v3 , v5 } =⇒ deg(v3 ) = 3. N(v5 ) := {v4 , v2 } =⇒ deg(v3 ) = 2. Thus △(G) = 4 and δ(G) = 1. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 49/56 What is Graph Consider the graph H below Question: What is the maximum and minumum degree of H Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 50/56 What is Graph Consider the graph H below Question: What is the maximum and minumum degree of H Solution: N(u) := {u, v, x} =⇒ deg(u) = 3. N(v) := {u, w, x} =⇒ deg(v) = 3. N(w) := {v, x} =⇒ deg(w) = 2. N(x) := {u, v, w, y} =⇒ deg(x) = 4. N(y) := {x} =⇒ deg(y) = 1. Thus △(H) = 4 and δ(H) = 1. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 51/56 What is Graph Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 52/56 What is Graph Consider the graph G below Question: Find d(G)? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 53/56 What is Graph Consider the graph G below Question: Find d(G)? Solution: N(v1 ) := {v2 } =⇒ deg(v1 ) = 1. N(v2 ) := {v1 , v3 , v4 , v5 } =⇒ deg(v2 ) = 4. N(v3 ) := {v2 , v3 , v4 } =⇒ deg(v3 ) = 3. N(v4 ) := {v2 , v3 , v5 } =⇒ deg(v3 ) = 3. N(v5 ) := {v4 , v2 } =⇒ deg(v3 ) = 2. Thus, d(G) = (4, 3, 3, 2, 1). Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 54/56 What is Graph Consider the graph H below Question: Find d(H)? Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 55/56 What is Graph Consider the graph H below Question: Find d(H)? Solution: N(u) := {u, v, x} =⇒ deg(u) = 3. N(v) := {u, w, x} =⇒ deg(v) = 3. N(w) := {v, x} =⇒ deg(w) = 2. N(x) := {u, v, w, y} =⇒ deg(x) = 4. N(y) := {x} =⇒ deg(y) = 1. Thus, d(H) = (4, 3, 3, 2, 1). Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14  History What is Graph 56/56 Exercise. Consider the graph below. Sir Rafa [DMS] Math 20223 Graph Theory with Application 2024-11-14