Chapter_04_Presentation.pdf

Graph Theory Chapter 04 MS. M.W.S. Randunu Department of Interdisiplinary Studies,University of Ruhuna. July 17, 2024 1/102 Graph A graph G = (V , E) consists...

Graph Theory Chapter 04 MS. M.W.S. Randunu Department of Interdisiplinary Studies,University of Ruhuna. July 17, 2024 1/102 Graph A graph G = (V , E) consists of V , a nonempty set of vertices (or nodes), and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. ▶ The order of a graph refers to the number of vertices it contains, denoted by |V |. ▶ The size of a graph refers to the number of edges it contains, denoted by |E|. 2/102 Examples B A D C ▶ Order: 4 (vertices A, B, C, and D) ▶ Size: 5 (edges AB, AC, BC,BD and CD) 3/102  B C A D F E 4/102 Note: The set of vertices V in a graph G can be infinite. A graph with an infinite number of vertices or edges is referred to as an infinite graph. Conversely, a graph with a finite number of vertices and edges is termed a finite graph. 5/102 In a network consisting of data centers and communication links between computers, each data center can be represented by a point, and each communication link by a line segment. 6/102 Anuradhapura Jaffna Kandy Colombo Galle Matara Figure: A Computer Network 7/102 Simple Graph A simple graph is a graph in which each edge connects two different vertices, and no two different edges connect the same pair of vertices. B A D C Figure: Simple graph with vertices and edges. 8/102 Multigraph A multigraph is a graph that may have multiple edges connecting the same pair of vertices. B A C Figure: A multigraph with multiple edges between vertices A, B, and C. 9/102 When there are m different edges associated with the same unordered pair of vertices {u, v }, we also say that {u, v } is an edge of multiplicity m. That is, we can think of this set of edges as m different copies of an edge {u, v }. 10/102 In some cases, a communications link connects a data center to itself.To model this network, we need to include edges that connect a vertex to itself, known as loops. A B C Figure: Undirected Graph with Loops 11/102 Directed Graph A directed graph (or digraph) (V , E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. B A D C Figure: A directed graph with vertices A, B, C, and D. 12/102 In a directed graph, arrows indicate the direction of edges. Each arrow points from one vertex u to another vertex v , showing that the edge starts at u and ends at v. Directed graphs can have: 1. Loops: An edge that points back to the same vertex. 2. Multiple edges: More than one edge between the same pair of vertices. 3. Bidirectional Edges: Edges going in both directions between two vertices. 13/102 Simple Directed Graph A simple directed graph has no loops or multiple edges between the same pair of vertices. In such graphs, each pair of vertices (u, v ) has at most one edge. If there are m directed edges associated with the ordered pair of vertices (u, v ), we say that (u, v ) is an edge of multiplicity m. 14/102 Example: Imagine we have a group of people: Alice (A), Bob (B), Charlie (C), Diana (D), and Eve (E). They know each other as follows: ▶ Alice knows Bob and Charlie. ▶ Bob knows Charlie and Diana. ▶ Charlie knows Diana and Eve. ▶ Diana knows Eve. We will represent these relationships with a graph. C D A B E 15/102 Basic Terminology Degree The degree of a vertex v in an undirected graph is defined as the number of edges incident with it. However, if there is a loop at vertex v , it contributes twice to the degree of that vertex. The degree of vertex v is denoted by deg(v ). 16/102 Examples: Consider a graph with vertices A, B, C, and D. Q P S R ▶ deg(P) = 2 ▶ deg(Q) = 3 ▶ deg(R) = 2 ▶ deg(S) = 1 17/102 Consider a graph with vertices A, B, C,D, E and F. C D A B E F 18/102 In an undirected graph G, two vertices u and v are considered adjacent or neighbors if they share an edge e. This edge e is incident with both vertices u and v , and it connects them. The vertex u is the initial vertex of the edge (u, v ), and v is the terminal or end vertex of that edge. If there’s a loop at a vertex, the initial and terminal vertices of that loop are the same. 19/102 Example: Consider an undirected graph G with vertices A, B, C, and D. A B D C ▶ Vertices A and B are adjacent ▶ Vertices A and C are adjacent. ▶ Vertices B and D are adjacent ▶ Vertices C and D are adjacent 20/102 In a graph with directed edges, if there’s an edge (u, v ), then we say that u is adjacent to v , and v is adjacent from u. 21/102 Example: Consider a directed graph G with vertices V = {A, B, C, D} and edges E = {(A, B), (B, C), (C, D), (D, A)}. B A D C 22/102 In a graph with directed edges, ▶ The in-degree of a vertex v , denoted by deg− (v ), is the number of edges with v as their terminal vertex. ▶ The out-degree of v , denoted by deg+ (v ), is the number of edges with v as their initial vertex. Note: A loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex. 23/102 Exercise: Consider the directed graph shown below: B A D C What is the out-degree of vertex C? What about the in-degree of vertex D? 24/102 Degree Sequence The degree sequence of a graph is a sequence of its vertex degrees in non-increasing order. For directed graphs, we have both in-degrees and out-degrees. 25/102 Example: Consider the graph G with vertices V = {A, B, C, D} and edges E = {(A, B), (A, C), (B, C), (C, D)}. B D A C Degree Sequence: ▶ Arranged in non-increasing order: {3, 2, 2, 1} Note: ▶ Minimum Degree: The smallest degree of any vertex in the graph. ▶ Maximum Degree: The largest degree of any vertex in the graph. 26/102 Theorem 1: Let G = (V , E) be a graph with directed edges. Then, P − P + v ∈V deg (v ) = v ∈V deg (v ) = |E| Handshaking Theorem Let G = (V , E) be an undirected graph with m edges. Then the sum of the degrees of all vertices is equal to twice the number of edges. X 2m = deg(v ) v ∈V Note: This theorem applies even if multiple edges and loops are present. 27/102 Example: B D A C The sum of the degrees is: deg(A) + deg(B) + deg(C) + deg(D) = 3 + 2 + 3 + 2 = 10 Since there are 5 edges, according to the Handshaking Theorem: 2m = 2 × 5 = 10 Therefore: X deg(v ) = 10 v ∈V 28/102 Example: A graph has 10 edges and each vertex has a degree of 3. How many vertices does this graph have? 29/102 Lemma 1: An undirected graph has an even number of vertices of odd degree. Proof: Let V1 and V2 be the set of vertices of even degree and the set of vertices of odd degree, respectively, in an undirected graph G = (V , E) with m edges. Then X X X 2m = deg(v ) = deg(v ) + deg(v ). v ∈V v ∈V1 v ∈V2 Because deg(v ) is even for v ∈ V1 , the first term on the right-hand side of the last equality is even. Furthermore, the sum of the two terms on the right-hand side of the last equality is even, because this sum is 2m. Hence, the second term in the sum is also even. Because all the terms in this sum are odd, there must be an even number of such terms. Thus, there are an even number of vertices of odd degree. 30/102 Example: Consider the following graph: 1 2 5 4 3 Let’s apply the handshake lemma to this graph: The sum of the degrees of all vertices is 2 + 3 + 3 + 2 + 2 = 12. Since each edge contributes 2 to the sum of degrees (1 for each endpoint), and there are 6 edges in total, the total sum is 2 × 6 = 12, which matches the sum of the degrees of all vertices. 31/102 Example: 1 2 3 4 5 6 7 8 9 32/102 Adjacency Matrices The adjacency matrix A of a graph G with n vertices is an n × n matrix where each element aij is defined as follows: ( 1 if there is an edge between vertices i and j aij = 0 otherwise In an undirected graph, the adjacency matrix is symmetric, while in a directed graph, it may not be symmetric. 33/102 Example: Consider an undirected graph with 4 vertices labeled A, B, C, and D. B A C D The adjacency matrix A for this graph would be:   0 1 0 1 1 0 1 0 A= 0 1 0 1  1 0 1 0 34/102 Exercise: For the directed graph below, what is the adjacency matrix? B A C 35/102 Example: Draw a graph with the adjacency matrix   0 1 1 0 0 1 0 1 1 0   1 1 0 0 1   0 1 0 0 1 0 0 1 1 0 with respect to the ordering of vertices P, Q, R, S, T. Solution: T Q P S R 36/102 Note: ▶ The adjacency matrix of a simple graph is symmetric, meaning aij = aji , because both entries are 1 when vi and vj are adjacent, and both are 0 otherwise. ▶ Additionally, in a simple graph with no loops, each diagonal entry aii , where i = 1, 2, 3,... , n, is always 0. 37/102 Incidence Matrices Consider a graph G = (V , E) with n vertices and m edges. The vertex-edge incidence matrix M of G is an n × m matrix such that: ▶ If vertex vi is incident with edge ej , then Mij = 1. ▶ If vertex vi is not incident with edge ej , then Mij = 0. In other words, each row of the matrix represents a vertex, each column represents an edge, and the entry Mij is 1 if vertex vi is incident with edge ej , and 0 otherwise. 38/102 Example: e1 A B e2 e53 e6 C D e4 We have a graph with vertices A, B, C, D and edges e1 , e2 , e3 , e4 , e5 , e6. The incidence matrix for this graph is given by:   1 1 0 0 1 0 1 0 1 0 0 1   0 1 1 1 0 0 0 0 0 1 1 1 39/102 Exercise: Write down the incidence matrix for the graph with vertices A, B, C, D, E and edges e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8. e1 B e84 A e63 D e2 e5 C e7 E 40/102 Neighborhood The set of all neighbors of a vertex v in a graph G = (V , E), denoted by N(v ), is called the neighborhood of v. If A is a subset of V , the set of all vertices in G that are adjacent to at least one vertex in A is denoted by N(A). [ N(A) = N(v ) v ∈A 41/102 Example: Consider a graph G with vertices {1, 2, 3, 4, 5} and edges {(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)}. 2 1 4 5 3 42/102 Neighborhood of a single vertex: ▶ N(1) = {2, 3} ▶ N(2) = {1, 4} ▶ N(3) = {1, 4} ▶ N(4) = {2, 3, 5} ▶ N(5) = {4} Neighborhood of a subset of vertices: ▶ For A = {1, 2}: N(A) = N({1, 2}) = N(1)∪N(2) = {2, 3}∪{1, 4} = {1, 2, 3, 4} 43/102 Connectivity Walk Given a graph G = (V , E), a walk of length l is defined as a sequence v0 , e1 , v1 , e2 , v2 ,... , vl−1 , el , vl consisting of vertices v0 , v1 , v2 ,... , vl−1 , vl and edges e1 , e2 , e3 ,... , el such that each edge ei is incident to the vertices vi−1 and vi. Generally, the ei ’s and vi ’s do not need to be distinct. The length of a walk is defined as the number of edges it contains. 44/102 Example: Consider the following graph G: A B D C A possible walk of length 4 in this graph could be: A, (A, B), B, (B, D), D, (D, A), A, (A, B), B 45/102 Types of Walks 1. Open Walk: ▶ It starts at one vertex and ends at another, allowing for the possibility of revisiting vertices and edges along the way. 2. Closed Walk: ▶ It forms a loop, starting and ending at the same vertex, potentially revisiting other vertices and edges in between. 3. Trail: ▶ It does not repeat any edges, although it may revisit vertices. ▶ Trails can be open or closed. 4. Circuit: ▶ It forms a closed loop, revisiting the starting vertex after traversing a sequence of edges and vertices. ▶ Circuits may or may not repeat edges, but they do not repeat vertices other than the starting and ending vertex. 46/102 Example: Consider the graph G with vertices A, B, C, D and edges (A, B), (B, C), (C, D), (D, A), (B, D). A B D C ▶ Open Walk: A → B → D ▶ Closed Walk: A → B → C → D → A ▶ Trail: A → B → C → D ▶ Circuit: A → B → D → A 47/102 Path A path in a graph is a sequence of vertices where each adjacent pair of vertices is connected by an edge. In other words, a path is a walk in which all edges and all vertices are distinct. ▶ Simple Path: A path that does not repeat any vertices (except possibly the first and last vertices if the path is a cycle). ▶ In an undirected graph, a path can traverse edges in any direction. ▶ In a directed graph (digraph), a path must follow the direction of the edges. 48/102 Cycle A cycle in a graph G = (V , E) is a non-empty sequence of vertices v0 , v1 , v2 ,... , vk and edges e1 , e2 , e3 ,... , ek such that: 1. Each edge ei is incident to the vertices vi−1 and vi for 1 ≤ i ≤ k. 2. The sequence forms a loop, i.e., v0 = vk , where v0 , v1 ,... , vk are distinct vertices (except v0 = vk ). 49/102 Example: Consider the following graph G with vertices A, B, C, D and edges (A, B), (B, C), (C, D), (D, A), (B, D). A B D C The cycle A → B → D → A forms a closed loop by starting and ending at vertex A. 50/102 Connected An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. An undirected graph that is not connected is called disconnected. Strongly Connected A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. 51/102 A C B D 52/102 Weakly Connected A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph. A B C 53/102 Euler and Hamilton Paths Is there a simple circuit in this multigraph that includes every edge? 54/102 Euler Circuit An Euler circuit in a graph G is a simple circuit containing every edge of G. 55/102 Example: Consider the following graph G: A B C D E F ▶ An Euler circuit would be a simple circuit that starts and ends at the same vertex, visiting every edge exactly once. A → B → C → F → E → D → A. ▶ An Euler path would be a simple path that visits every edge exactly once. A → B → C → F → E → D. 56/102 Eulerian Graph An Eulerian graph is a graph that contains an Euler circuit, which is a simple circuit that includes every edge of the graph exactly once. For a graph to be Eulerian, it must be connected, and every vertex must have an even degree. 57/102 Theorem 3: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has an even degree. 58/102 Example: Consider a graph G = (V , E) V = {1, 2, 3, 4, 5} E = {(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)} In this graph, vertices 2, 3, and 4 have odd degrees. Therefore, the graph G is not Eulerian because it does not satisfy the condition that all vertices must have even degree. Exercise: Consider a graph G = (V , E) V = {1, 2, 3, 4, 5} E = {(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (4, 5)} Determine whether G is Eulerian. 59/102 Hamilton Paths and Circuits Hamilton Path A Hamilton path is a path that visits every vertex in the graph exactly once. 2 1 3 4 In this example, the path 1 → 2 → 3 → 4 is a Hamiltonian path. 60/102 Hamilton Circuit A Hamilton circuit is a circuit that starts and ends at the same vertex and visits every other vertex exactly once. 2 1 3 4 In this example, the circuit 1 → 2 → 3 → 4 → 1 is a Hamiltonian circuit. 61/102 Hamiltonian Graph A Hamiltonian graph is a graph that contains a Hamilton circuit. 1 4 2 3 In this example, the graph contains a Hamiltonian circuit 1 → 2 → 3 → 4 → 1, making it a Hamiltonian graph. 62/102 63/102 Dirac’s Theorem: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit. Ore’s Theorem: If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v ) ≥ n for every pair of non-adjacent vertices u and v in G, then G has a Hamiltonian circuit. 64/102 Girth of a Graph The girth of a graph G = (V , E) is defined as the length of the smallest cycle, provided that the graph has at least one cycle. If the graph has no cycles, the girth of the graph is defined as ∞. Diameter of a Graph The diameter of a graph G = (V , E), denoted by diam(G), is defined as the length of the shortest path between the most distanced pair of vertices of G. That is, diam(G) = max{ℓ(u, v ) | u, v ∈ V } 65/102  Example: consider a graph G = (V , E) V = {1, 2, 3, 4, 5, 6, 7, 8} E = {(1, 2), (1, 4), (1, 6), (2, 3), (2, 4), (2, 6), (2, 8), (3, 5), (3, 7), (3,8), (4,5), (4,8), (5,6), (5,7), (6,8)} 1 2 7 vertices ▶ Find a circuit in G which is not a cycle. should 8 be 1→2→4→5→6→8→2→1 distinct ▶ Find a circuit in G which is also a cycle. 3 6 1→2→8→6→5→4→1 4 5 66/102 ▶ What is the diameter of G? Shortest path distances: 1 2 3 4 5 6 7 8 1 0 1 3 1 2 1 3 2 2 1 0 2 1 2 1 2 1 3 3 2 0 3 2 1 1 1 4 1 1 3 0 1 2 3 1 5 2 2 2 1 0 1 1 2 6 1 1 1 2 1 0 2 1 7 3 2 1 3 1 2 0 1 8 2 1 1 1 2 1 1 0 The maximum shortest path distance is 3, so the diameter of G is 3. ▶ What is the girth of the graph G? We’ve already found a cycle of length 4 (1 → 2 → 8 → 6 → 1), so the girth of G is 4. 67/102 ▶ Is the graph G Eulerian? Vertex Degree 1 3 2 5 3 3 4 3 5 3 6 4 7 2 8 4 Not all vertices have even degree, so the graph G is not Eulerian. ▶ Find a Hamiltonian path of the graph G. Hamiltonian path: 1 → 2 → 3 → 5 → 7 → 8 → 6 → 4 68/102 Complete Graph A complete graph on n vertices, denoted by Kn , is a simple graph that contains exactly one edge between each pair of distinct vertices. 1 1 1 1 2 2 2 3 4 3 Figure: Complete graphs K1 , K2 , K3 , K4 A simple graph for which there is at least one pair of distinct vertices not connected by an edge is called non-complete. 69/102 Cycle Graph A graph is called a cycle graph if it consists only of a single cycle and all vertices are incident to exactly two edges of the cycle. A cycle containing n vertices is denoted by Cn. C3 C4 Figure: Cycle graphs C3 , and C4 70/102 Wheel Graph We obtain a wheel graph Wn when we add an additional vertex to a cycle Cn , for n ≥ 3, and connect this new vertex to each of the n vertices in Cn by new edges. 71/102 Regular Graph A graph is called regular if all of its vertices have the same degree. Specifically, a graph G = (V , E) is k -regular if every vertex in V has degree k , where k is a non-negative integer. Figure: Regular graphs: 3-regular, 4-regular, 5-regular, and 6-regular 72/102 Edgeless Graphs An edgeless graph, also known as a null graph or an empty graph, is a graph with no edges and denoted by (Kn ), where n is the number of vertices. It consists only of vertices and no connections between them. Figure: Edgeless graph with 4 vertices 73/102 Bipartite Graphs A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2 ). When this condition holds, we call the pair (V1 , V2 ) a bipartition of the vertex set V of G. Figure: Examples of bipartite graphs 74/102 Complete Bipartite Graphs A complete bipartite graph Km,n is a graph that has its vertex set partitioned into two subsets of m and n vertices, respectively, with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. U2 U1 Figure: Complete bipartite graph K3,4 75/102 76/102 Job Assignments: Suppose there are m employees and n different jobs, where m ≥ n. Each employee is trained to do one or more of these n jobs. We want to assign an employee to each job. To model this, we use a bipartite graph: ▶ Represent each employee by a vertex in set E. ▶ Represent each job by a vertex in set J. ▶ Draw an edge from an employee to a job if the employee is trained to do that job. J (Jobs) E (Employees) J4 E3 J3 E2 J2 E1 J1 77/102 Marriages on an Island: Suppose there are m men and n women on an island. Each person has a list of members of the opposite gender acceptable as a spouse. We construct a bipartite graph G = (V1 , V2 ), where V1 is the set of men and V2 is the set of women. There is an edge between a man and a woman if they find each other acceptable as a spouse. A matching in this graph consists of a set of edges, where each pair of endpoints of an edge is a husband-wife pair. A maximum matching is the largest possible set of married couples, and a complete matching of V1 is a set of married couples where every man is married, but possibly not all women. 78/102 Trees A tree is a connected acyclic graph. This means that a tree has the following properties: 1. No Cycles 2. Connectedness 3. A cyclic A B C D E Figure: A simple tree 79/102 In a tree G = (V , E), the number of edges |E(G)| is one less than the number of vertices |V (G)|. |E(G)| = |V (G)| − 1 Example: A B C D E In this tree, |V (G)| = 5 and |E(G)| = 4. |E(G)| = |V (G)| − 1, 4 = 5 − 1. 80/102 Forest A forest is a graph in which any two vertices are connected by at most one simple path. In other words, a forest is an undirected graph without cycles. A forest can be a disjoint union of one or more trees. 81/102  B F A D E C G Figure: Example of a forest but not a tree B F A D E C G Figure: Example of not a tree and not a forest 82/102 Figure: Example of both a tree and a forest 83/102 Binary Trees A binary tree is a tree with exactly one vertex of degree two, such that all the other vertices have degree one or three. ▶ Root Node: The topmost node of the binary tree. ▶ Leaf Nodes: Nodes that have no children. They are the nodes with degree one. ▶ Trivalent Vertices: Nodes that have exactly three children. They are the nodes with degree three. 84/102  Root 1 Left Child(Leaf Node) 2 3 Right Child Trivalent Vertex 5 6 Leaf Node Leaf Node Figure: Binary tree 85/102 Graph Isomorphism Two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are said to be isomorphic if there exists a bijection f : V1 → V2 such that {u, v } ∈ E1 if and only if {f (u), f (v )} ∈ E2. Method One – Checklist 1. Number of Vertices 2. Number of Edges 3. Degree Sequence 4. Cycles of Length k 86/102 Example: 1. Are the number of vertices in both graphs the same? Yes. 2. Are the number of edges in both graphs the same? Yes. 3. Is the degree sequence in both graphs the same? Yes. 4. If the vertices in one graph can form a cycle of length k, can we find the same cycle length in the other graph? Yes... 87/102 Method Two – Relabeling 1. Identify Vertices and Degrees: Start with the vertices with the highest degree and label them. 2. Label Adjacent Vertices: Identify vertices that are adjacent to the already labeled vertices. 3. Continue Labeling: Continue this process until all vertices are labeled. 4. Define Isomorphism: Verify the one-to-one correspondence between the vertices of the two graphs. 88/102 Example: ▶ Both graphs have 5 vertices. ▶ Degree sequence (in ascending order): (2, 2, 2, 3, 3). 89/102 Now we methodically start labeling vertices by beginning with the vertices of degree 3 and marking a and b. Next, we notice that in both graphs, there is a vertex that is adjacent to both a and b, so we label this vertex c in both graphs. 90/102 This now follows that there are two vertices left, and we label them according to d and e, where d is adjacent to a and e is adjacent to b. 91/102 And finally, we define our isomorphism by relabeling each graph and verifying one-to-correspondence. 92/102 For the following two examples, you will see that the degree sequence is the best way for us to determine if two graphs are isomorphic. 93/102 Properties of Isomorphic Graphs Isomorphic graphs share several properties: ▶ Same number of vertices and edges ▶ Vertex degrees ▶ Subgraph structure ▶ Cycles 94/102 Complement of a Graph The complement of a graph G, denoted as G, is a graph that contains exactly the same set of vertices as G, but its edges connect pairs of vertices that are not adjacent in G, and vice versa. Formally, if G = (V , E) is a graph, then its complement G = (V , E), where E consists of all possible edges between vertices in V that are not already in E. A B A B C D C D (a) Graph G (b) Complement G 95/102 Planar Graphs A graph is called planar if it can be drawn in the plane without any edges crossing. Such a drawing is called a planar representation of the graph. B A C F D E Figure: Planar Graph G C 96/102 Graph Coloring A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. Steps for Graph Coloring 1. Identify Vertices and Edges: Begin by identifying all the vertices and edges in the graph. 2. Choose a Color: Start with the first vertex and assign it the first color. 3. Color Adjacent Vertices: Move to the next vertex. If it is adjacent to any previously colored vertices, choose a different color. 4. Continue Coloring: Repeat the process for all vertices, ensuring that no two adjacent vertices share the same color. 97/102 Chromatic Number The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by χ(G). Example: V = {A, B, C, D, E} E = {(A, B), (A, C), (B, C), (B, D), (C, D), (D, E)} A B E D C By using three different colors, we ensured that no two adjacent vertices share the same color. Thus, the chromatic number for this graph is 3. 98/102 The Four Color Theorem The chromatic number of a planar graph is no greater than four. B E F A C H G D Figure: A Planar Graph Colored with Four Colors 99/102 ▶ Map Coloring: Ensuring that no two adjacent regions on a map share the same color. ▶ Scheduling: Assigning time slots to tasks or exams so that no two overlapping tasks share the same slot. ▶ Register Allocation: In compiler design, assigning variables to a limited number of CPU registers. 100/102 Edge coloring Edge coloring involves coloring the edges of a graph so that no two edges that share the same vertex have the same color. The chromatic index χ′ (G) is the minimum number of colors needed for edge coloring. 101/102 Example Consider the following bipartite graph K3,3 with 6 vertices: 1 4 2 5 3 6 Figure: Edge Coloring Example for K3,3 In this example, we use three colors (red, blue, and green) to color the edges of the bipartite graph K3,3. The chromatic index χ′ (G) for this graph is 3 because we need at least 3 colors to ensure that no two edges sharing the same vertex have the same color. 102/102