Discrete Math concepts of National Level Exam (Previous Questions)

1. The number of integers between 1 and 250 that are divisible by 2, 5 and 7 is
(A) 2 (B) 3
(C) 5 (D) 8

2*5*7=70
250/70=3.___=3=B

Concept
Numbers which can be divisible by any of the three: n(A) + n(B) + n(C) - n(A and B) - n(B and C) - n(A and C) + n(A and B and C)
Numbers which can be divisible by all three: n(A and B and C)
Numbers which can be divisible by atleast two of three: n(A and B) - n(B and C) - n(A and C) + n(A and B and C)


2. An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are
(A) all of even degree
(B) all of odd degree
(C) of any degree
(D) even in number

An Euler path is a path that uses every edge of a graph exactly once. 

An Euler path starts and ends at different vertices.

An Euler circuit is a circuit that uses every edge of a graph exactly once.

An Euler circuit starts and ends at the same vertex.

It may cross/ repeat vertices but not edges

If number of odd vertices in path is exactly 2, then it is Euler Path,

If a graph G has an Euler circuit, then all of its vertices must be even vertices.

In every graph, the sum of the degrees of all vertices equals twice the number of edges. 

To find an Euler path or an Euler circuit:

1. Make sure the graph has either 0 or 2 odd vertices. 
2. If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them. 
3. Follow edges one at a time. If you have a choice between a bridge and a non-bridge, always choose the non-bridge. 
4. Stop when you run out of edges. 

This is called Fleury’s algorithm, and it always works!