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 - 1
Date: 16/10/2023
Course Code &Title: 18MAB302T - Discrete Mathematics for Engineers
Year & Sem: III/V
Q. No Questions Answer Keys
1 Use Kruskal’s algorithm to find a minimum spanning tree for the
following weighted graph.
A 1 B
2 3
4 E 3
3 2
C 1 D
2 Draw the graph 5 vertices A, B, C, D, E such that deg(A) = 3,
B is an odd vertex, deg(C) = 2 and D and E are adjacent.
3 Prove that the number of vertices of odd degree in an undirected graph
is even.
4. Prove that a tree with n vertices has (n-1) edges.
5. Find the number of edges in K6. (c) 15
6. Draw the graph for the given adjacency matrix
1 2 0 1
2 0 3 0
0 3 1 1
1 0 1 0
7. Find the number of vertices, then number of edges and the degree
of each vertex in the following undirected graph. Verify also the
handshaking theorem.
D C
E B
A
Justify whether the following graphs are isomorphic or not.
8. A D V1 V4
B C V2 V3
G1 G2
9. For each of the following degree sequence, find if there exist a
graph. In each case, either draw a graph or explain why no graphs
exists.
(a) 4, 4, 4, 3, 2 (b) 5, 4, 3, 2, 1, 1
10. Prove that the number of edges in a bipartite graph with a vertices
is at most (n2/2).
