SRM Institute of Science and Technology
College of Engineering and Technology
Department of Mathematics
SRM Nagar, Kattankulathur – 603203, Chengalpattu District, Tamil Nadu
Academic Year: 2023-2024(odd)
Tutorial sheet - 3
Date: 16/10/2023
Course Code &Title: 18MAB302T - Discrete Mathematics for Engineers
Year & Sem: III/V
Q. No Questions Answer Keys
1 Draw all the spanning trees of the graph
A B
C D
2 Find the minimum spanning tree for the following weighted (c) 2
graph using Kruskal’s algorithm
A 41 B 32 C 29 D
21 42 43 23
22 31 44
E 20 F 62 G 45 H
3 Prove that the maximum number of edges in a simple disconnected
(𝑛−𝑘)(𝑛−𝑘+1)
graph G with n vertices and k components is .
2
4. Give an example of a graph which contains an Eulerian
circuit but not a Hamiltonian circuit.
5. If a graph G has 7 vertices then find its chromatic number.
6. A simple graph in which there is exactly one edge between each Complete graph
pair of distinct vertices is called _____
7. Define adjacency matrix of a graph G. Draw the graphs represented
by the following adjacency matrix
𝐴 0 1 1 1
𝐵 1 0 0 0
𝐶 1 0 0 1
𝐷 1 0 1 0
Verify the handshaking theorem for the following graphs
8.
i) A B
C D
(ii) A B D
E F G
9. Prove that an undirected graph is a tree if and only if there
is a unique simple path between every pair of vertices.
10. Find the number of paths of length 4 from the vertex D to the vertex
E in the following undirected graph and identify those paths from
the graph.
A B
C
D E
