Applied Mathematics - II: Graph Theory PDF

# Applied Mathematics - II: Graph Theory ## Chapter 3: Graph Theory ### 1. Introduction - The "graphs" of graph theory differ from the graphs of functions. - Informally, a graph consists of vertices and edges. - Example: Connect two people by an edge if they have met. - Graph theory helps answer...

# Applied Mathematics - II: Graph Theory ## Chapter 3: Graph Theory ### 1. Introduction - The "graphs" of graph theory differ from the graphs of functions. - Informally, a graph consists of vertices and edges. - Example: Connect two people by an edge if they have met. - Graph theory helps answer questions about acquaintance, chemical bonding, electrical networks, transportation networks, binary vectors, etc. - Techniques include induction, parity, extremality, counting two ways, the Pigeonhole Principle, Inclusion-Exclusion and even the Dart Board Problem. ### 2. Graph #### Definition - A graph G = (V, E) consists of: - A set V = {v₁, v2, ..., vn...} whose elements are called **vertices** - A set E = {e1, e2, e3, ...} whose elements are called **edges**. - Each edge e₁ in E is associated with an unordered pair {vj, vk} of vertices, called the **end vertices** of e₁. #### Example 1: - V = {a, b, c, d, e} - E = {e1, e2, e3, e4, e5, e6, e7, e8} - {(a, b), (b, c), (c, c), (c, d), (b, d), (d, e), (b, e), (b, e)} #### Diagrammatic Representation: - A graph with 5 vertices and 8 edges. ### 3. Elementary Terminologies and Results - **Loop**: If both end vertices of an edge are identical, then such an edge is called a loop. - **Parallel (or Multiple) Edges**: If two (or more) edges of graph G have the same end vertices then these edges are called parallel (or multiple) edges. - **Degree (or Valency) of vertex**: The number of edges incident of vertex V is called degree (or valency) of v and it is denoted by d(v). - **Isolated Vertex**: A vertex of degree zero, is called an isolated vertex. - **Pendent Vertex**: A vertex of degree 1, is called a pendent vertex. - **Simple Graph**: A graph G is called simple if it has no loops and no parallel (multiple) edges. A graph which is not simple is called a **multigraph**. - **(n, m) graph**: A graph on *n* vertices with *m* edges is known as an (n, m) graph. - **Handshaking Lemma**: Let G = (V, E) be any graph, then Σd(v) = 2m = 2 (number of edges in G) #### Example: - How many edges are there in a graph with 10 vertices each of degree 6? - **Solution**: Total degree of the graph is ∑d(v) = 2m, where m is the number of edges. - There are 10 vertices, each with degree 6. - So, 10 * 6 = 2m or m = 30. - The number of edges is 30. #### Odd or Even Vertex: - A vertex of a graph is called odd or even depending on whether its degree is odd or even. #### Theorem: - In any graph G there is an even number of odd vertices. #### Proof: - Let W be the set of odd vertices of G and let U be the set of even vertices of G. - For each u∈U, d(u) is even and so Σd(u) is even. - However, Σd(u) + Σd(w) = Σd(v) = 2m. - Σd(w) = 2m – Σd(u) is even. - Since all the terms in Σd(w) are odd and their sum is even, there must be an even number of them. ### 4. Graphs as Models #### Problem 1: - We have 5 people A, B, C, D, E and 5 jobs a, b, c, d, e. - Some people are qualified for certain jobs. - Can we allocate one job to each person? #### Solution: - Represent the situation by a graph. - Vertices represent people and jobs. - Edges connect people to jobs they are qualified for. - There is no feasible way to allocate one job to each person because A, B, and D are only qualified for jobs c and d. #### Problem 2: - Graph G represents a network of telephone lines and poles. - We want to identify those lines and poles that must stay in service to avoid disconnection. #### Solution: - The network will disconnect if we remove the two lines represented by the edges connecting each of the two poles with the rest of the network. - Removing a single line will not cause a disconnection, but removing a single pole will cause a disconnection. ### 5. Special Types of Graphs - **Null Graph**: A graph G = (V, E) is called a null graph if the edge set E is empty, i.e., G has no edges. - **Complete Graph**: A simple graph G is called a complete graph if there is an edge between each pair of vertices. - **Regular Graph**: If every vertex of graph G is of the same degree K, we say that G is K-regular. - **Bipartite Graph**: Let G be a graph. If the vertex set V of G can be partitioned into two non-empty subsets V₁ and V₂ such that each edge in G has one end vertex in V₁ and the other end vertex V₂, then G is called a Bipartite Graph. ### 6. Subgraphs #### Definition - A graph H = (V(H), E(H)) is called a subgraph of a graph G = (V(G), E(G)) if V(H) ⊆ V(G) and E(H) ⊆ E(G). - **Proper Subgraph**: If H ⊆ G but H ≠ G, then H is called a proper subgraph of G. - **Spanning Subgraph**: A spanning subgraph of G is a subgraph H with V(H) = V(G). - **Vertex Deleted Subgraph**: If G = (V, E) is a graph with more than two vertices and v ∈ V be any vertex, then the graph G – v is subgraph of G with vertex set V – {v} and whose edges are all those of G which are not incident with v. - **Edge Deleted Subgraph**: If G = (V, E) is a graph and e is an edge of G then G – e is subgraph of G having vertex V and edge set E – {e}. #### Examples: - Vertex Deleted Subgraph: - Obtained from G by deleting vertex v3 and all edges incident on v3. - G - v3 is a subgraph of graph G obtained by deleting vertex v3. - G - v3 is a vertex deleted subgraph of G. - Edge Deleted Subgraph: - Obtained from G by deleting an edge e4 in G. - G - e4 is an edge deleted subgraph of G. ### 7. Induced Subgraphs #### Definition - **Vertex Induced Subgraph**: If U is a non-empty subset of the vertex set V of the graph G then the subgraph G<U> of G induced by U is defined to be the graph having vertex set U and edges consisting of those edges of G that have both ends in U. - **Edge Induced Subgraph**: If F is a non-empty subset of the edge set E of G then the subgraph G<F> induced by F is the graph whose vertex set is the set of ends of edges in F and whose edges is F. #### Example: - U = {v1, v4, v5, v6} - Vertex Induced subgraph: G<U> - F = {e2, e3, e6} - Edge Induced Subgraph is the graph whose vertices are the ends of the above edges and whose edges are e2, e3, and e6". ### 8. Walk, Trail, Path, Cycle in Graph #### Definition - **Walk**: A finite alternating sequence of vertices and edges. - **Trail**: A walk in which no edge is repeated. - **Path**: A walk in which no vertex is repeated. - **Cycle (or Circuit)**: A closed walk in which no vertex is repeated except terminal vertices. #### Examples: - **Walk**: v₁ e₁ v₂ e₅ v₃ e₁₀ v₃ e₅ v₂ e₃ v₅ - **Trail**: v₁ e₁ v₂ e₅ v₃ e₁₀ v₃ e₅ v₂ e₃ v₅ - All edges are distinct, but vertices v₁ and v₂ are repeated. - **Path**: v₂ e₄ v₄ e₈ v₃ e₇ v₅ e₆ v₁ - All vertices and edges are distinct. - **Cycle**: v₁ e₁ v₂ e₂ v₄ e₈ v₃ e₇ v₅ e₆ v₁ - All vertices and edges are distinct, and it's a closed walk. ### 9. Connected Graphs #### Definition - **Connected Graph**: A graph G is called connected if every two of its vertices are connected. - **Disconnected Graph**: A graph G is said to be disconnected if it is not connected. - **Component**: If u is a vertex of graph G, let C(u) denote the set of all vertices in G that are connected to u. Then the subgraph of G induced by C(u) is called the connected component containing u. #### Examples: - Consider graph H: - H is also disconnected graph having two connected components, i.e., W(H) = 2. - Consider graph: - The components of the graph can be seen in the image. #### Theorem 2: - Let G be a simple graph. Show that if G is not connected then its complement G is connected. #### Proof: - Let a simple graph G is not connected. - There exists two vertices u and v in G such that there is no edge joining u and v. - But the complement G of G contains those edges (of complement graph) which are not in G. - Since edge e = (u, v) ∉ E(G), then e ∈ E(G). - Hence in G any two vertices are connected, which means G, the complement of G, is connected. #### Theorem 3: - Agraph G is connected iff for every partition of its vertex set V(G) into two non-empty subsets V₁ and V₂ there exists an edge of G with one vertex in V₁ and other in V2. #### Proof: - **If G is connected**: - Suppose there is a partition {V₁, V₂} of V(G) such that there is no edge of G with one end vertex in V₁ and another in V₂. - Consider induced graphs G[V₁] and G[V₂] of G. - Every edge of G lies in G[V₁] or G[V₂], meaning G is a disjoint union of two of its subgraphs, which contradicts the fact that G is connected. - **If for every partition of V(G) into non-empty subsets V₁, V₂, there exists an edge of G with one end vertex in V₁ and another in V₂**: - Suppose that G is disconnected. - We want to prove that G is connected. - Let's suppose that G is disconnected, which means can be expressed as a disjoint union of subgraphs, such as G = G₁ ∪ G₂. - There does not exist an edge joining the vertex of G₁ and the vertex of G₂. - This contradicts our assumption that there exists an edge of G with one end vertex in V₁ and another in V₂. - Therefore, G must be connected. ### 10. Theorem 4: - If G is a simple (n, m) graph with k components then prove that n-k ≤ m. #### Proof: - The proof is by induction on *m*, the number of edges. - The base case is when *m* = 0. There are no edges, so the graph has *n* components, and *n* - *k* = 0. - Now, using the inductive hypothesis, we assume that the result is true for all simple graphs with less than *m* edges. - If there exists a subgraph with *m' - 1* edges and *(k + 1)* components, then the result holds for that subgraph, i.e., *n* - (*k* + 1) ≤ *m'* - 1. - But this subgraph has *m*’ ≤ *m*. - Combining these inequalities, we get n - k ≤ m’ ≤ m. - **Therefore, for a simple graph with *n* vertices, *m* edges, and *k* components, n - k ≤ m**. ### 11. Theorem 5: - If a graph has exactly two vertices of odd degree, then there must be a path between these two vertices. #### Proof: - **Case 1**: If G is connected, then by definition, there exists a u-v path. - **Case 2**: If G is disconnected, then G has two or more components. For definiteness, say G₁ and G₂ are the two components. - Suppose u lies in G₁ and v lies in G₂. - Since all other vertices of G are of even degree, G₁ has only one vertex, u, of odd degree, which contradicts that a graph has an even number of vertices of odd degree. - Therefore, u and v must lie in the same component (e.g., G₁). - Since G₁ is connected, there is a path between u and v. ### 12. Konigsberg Seven Bridge Problem - The Konigsberg Seven Bridge Problem is a classic problem in graph theory. - The city of Konigsberg was located on the Pregel River, with seven bridges connecting the banks and two islands in the river. - The problem was to find a way to walk through all seven bridges without crossing any bridge more than once. - Euler solved the problem and proved that it was impossible. ### 13. Theorem 6: - A graph G is bipartite if and only if all circuits (cycles) in G are of even length. #### Proof: - **If G is bipartite**: - Let V₁ and V₂ be the two sets of vertices in the bipartition, with every edge connecting one vertex from V₁ to a vertex from V₂. - Suppose there exists a cycle with odd length, k, in the graph. - Since the cycle alternates between vertices in V₁ and V₂, the starting and ending vertices of the cycle must be in the same set, which contradicts the definition of a cycle. - Therefore, every cycle in a bipartite graph has even length. - **If every cycle in G is of even length**: - Assume that G is connected. - Choose a vertex u. - Define V₁ as the set of all vertices that are an even distance from u and V₂ as the set of all vertices that are an odd distance from u. - It can be shown that no two vertices of V₁ are adjacent or no two vertices of V₂ are adjacent, which means the graph is bipartite. ### 14. Theorem 7: - If G is a self-complementary graph on *n* vertices, then *n* is of the type 4*k* or 4*k* + 1 for some integer *k*. #### Proof: - Let G be a self-complementary graph. - The complement of G, G, is isomorphic to G. - Let *m* be the number of edges in G. - m = n(n-1)/2 = *m as G = G - 4*m* = *n*(*n* - 1) - 4 divides *n*(*n* - 1) - Therefore, *n* is of the type 4*k* or 4*k* + 1. ### 15. Connected Graphs - A connected graph G is a graph where, for every pair of vertices, there is at least one path connecting them. - A disconnected graph has at least two separate components, where no vertices in one component share an edge with vertices in another. - The number of connected components in graph is represented as W(G). ### 16. Exercises - **Complete the problems as instructed in the document.**