Programme Name and Semester: B.
Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
Solutions of Home works for Module V: Graph Theory
B. Short Answer Type Questions:
1. A non-directed graph G has 8 edges. Write the number of vertices, if the degree of each
vertex in G is 2.
2. Calculate the total number of edges of a complete graph of 5 vertices.
3. Illustrate the concept of isomorphic graphs with some example.
Department of Mathema cs
Brainware University, Kolkata 1
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
Department of Mathema cs
Brainware University, Kolkata 2
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
4. Illustrate the concept of complete graph with examples.
5. Illustrate the concept of bipartite graph with examples.
6. Illustrate the definition of chromatic number for any graph.
Department of Mathema cs
Brainware University, Kolkata 3
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
7. Establish that if H is a subgraph of G, χ(H)≤ χ(G).
8. Explain the concept equality of two graphs and the concept of isomorphic graphs. Explain if
the following two graphs are isomorphic
Graph 1: V={a,b,c,d,e}, E={{a,b},{a,c},{a,e},{b,d},{b,e},{c,d}}.
Graph 2:
Department of Mathema cs
Brainware University, Kolkata 4
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
9. Show that any planar graph with v vertices and e edges satisfies the inequality e ≤ (3v−6).
Ans:
Department of Mathema cs
Brainware University, Kolkata 5
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
10. Give an example of a graph having chromatic number 6.
C. Long Answer Type Questions:
1. Calculate the graph from the following adjacency matrix:
Ans:
Department of Mathema cs
Brainware University, Kolkata 6
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
2. Explain adjacency matrix for a non-directed graph. Hence illustrate the adjacency matrix for
the following graph.
Ans:
Department of Mathema cs
Brainware University, Kolkata 7
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
3. Explain if the following graphs are isomorphic.
4. Construct the following graphs and examine the number of edges each of the following
graphs
(a)K4, (b)K3,2, (c)K1,5
Ans:
Department of Mathema cs
Brainware University, Kolkata 8
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
5.
Deduce that in any graph G the number of points of odd degree is even.
Department of Mathema cs
Brainware University, Kolkata 9
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
6. Deduce the Euler’s handshaking lemma.
Department of Mathema cs
Brainware University, Kolkata 10
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
7. Let G be a connected graph with n vertices. Then deduce that G is a tree if and only if e(G) =
n − 1.
Department of Mathema cs
Brainware University, Kolkata 11
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
Department of Mathema cs
Brainware University, Kolkata 12
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
8.
Explain that A graph G with n vertices, n-1 edges and no cycles is connected.
9.
Explain that every connected graph G has a spanning tree.
Ans:
Department of Mathema cs
Brainware University, Kolkata 13
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
10. Deduce the graph from the following incidence matrix
Ans:
Department of Mathema cs
Brainware University, Kolkata 14
Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
References:
1. “Discrete Mathematics and Its Applications”, Kenneth H. Rosen, McGraw-Hill.
2. “Discrete Mathematics with Applications”, Susanna S Epp, Wadsworth Publishing Co. Inc, 4th edition
3. “Elements of Discrete Mathematics: a computer oriented approach”, C L Liu and Mohapatra, McGraw
Hill, 3rd edition.
4. “Discrete Mathematical Structures and its Application to Computer Science”, J P Trembley, R
Manohar, TMG Edition, Tata McGraw-Hill.
5. “Discrete Mathematics”, Norman L Biggs, Oxford University Press, 2nd Edition.
6. “Discrete Mathematics”, Schaum’s Outlines Series, Semyour Lipschutz and Marc Lipson
Department of Mathema cs
Brainware University, Kolkata 15