Categories

# MA8351 Important Questions Discrete Mathematics

## Sample MA8351 Important Questions Discrete Mathematics:

1. The Handshaking Theorem
Let G = (V, E) be an undirected graph with ‘e’ edges. Then vV
deg(v) = 2е
The sum of degrees of all the verticies of an undirected graph is twice the number of edges of
the graph and hence even.
Proof: MA8351 Important Questions Discrete Mathematics
Since every edge is incident with exactly two vertices, every edges contributes 2 to the sum of
the degree of the vertices.
All the ‘e’ edges contributes (2e) to the sum of the degrees of vertices.
deg(v) = 2e
2. Draw the graph with 5 vertices, A, B, C, D, E such that deg(A) = 3, is an odd vertex, deg (C)
= 2 and D and E are adjacent. MA8351 Important Questions Discrete Mathematics
Solution:
d(E) = 5
d(C) = 2
d(D) = 5
d(A) = 3
d(B) = 1
3. In an undirected graph, the numbers of odd degree vertices a re even.
Proof: MA8351 Important Questions Discrete Mathematics
Let V1 and V2 be the set of all vertices of even degree and set of all v ertices
of odd degree, respectively, in a graph G= (V, E).

Therefore, d(v)= d(vi)+ d(vj)
By handshaking theorem, we have
Since each deg (vi) is even, is even.
As left hand side of equation (1) is even and the first expression on the RHS of (1) is
even, we have the 2nd expression on the RHS must be even.
Since each deg (vj) is odd, the number of terms contained in i.e., The number of
vertices of odd degree is even. MA8351 Important Questions Discrete Mathematics
4. If the simple graph G has 4 vertices and 5edges, then how many edges does Gc have?
Solution:
( ) c E GG =
2
 ( 1)
E(G) + ( ) c E G =
2
 ( 1)
e+ ( ) c E G =
2
 ( 1)
( ) c E G =
2
 ( 1)
 Gc has
2
 ( 1)
– e edges
 Gc have
2
4(4 1)
– 5 = 6 – 5 = 1 edges.
5. How many edges are there in a graph with ten vertices each of degree six.
Solution: MA8351 Important Questions Discrete Mathematics
Let e be the number of edges of the graph.
2e = Sum of all degrees
 = 10*6 = 60.
 2e = 60 e = 30. There are 30 edges.

 Subject name Discrete Mathematics Semester 3 Subject Code MA8351 Regulation 2017 regulation