ii) Define graph isomorphism and give an example of isomorphic and non-

isomorphic graphs
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 14.(a)(i)Show that if G is a simple graph with n vertices and K components, then the number
CAT II: SEP 2018 of edges is at most ( n  k ) ( n  k + 1 ) / 2.
MA8351-DISCRETE MATHEMATICS (a)(ii) Using the method of generating function, solve the recurrence relation
Year/Sem : II/III Date : .2018
Class/Section : II CSE A and B Duration : 3 Hours sn  3sn1  4s n2  0; n  2 Given that s 0  3 and s1  2
Faculty : M.TAMIL MOZHI Max. Marks : 100 OR
Answer ALL Questions .(b)(i)Define Euler graph and Hamiltonian graph. Give an example of (1)a graph which is
Part – A (10*2=20) Hamiltonian but not Eulerian, (2) a graph which is Eulerian but not Hamiltonian, (3)a graph
1. State the pigeonhole principle. which is neither Eulerian nor Hamiltonian.
2. How many permutations are there in the word M I S S I S S I P P I? (b)(ii)Using mathematical induction show that
3. Use mathematical induction to show that 𝑛! ≥ 2𝑛−1 , 𝑛 = 1,2,3, … 3n1  1
 3  for2 the. following graphs
n r

Find the recurrence relation satisfying the equation y n  A(3)  B (4) .

n n r 0
15.(a)(i)Define isomorphism. Establish as isomorphism
4.
5. State the principle of strong induction.
6. How many edges are there in a graph with 10 vertices each of degree 3?
7. Is K3 is bipartite.
8. Define Pseudograph.
9. Define bipartite graph.
10. Draw the graph with 5 vertices, A,B,C,D,E such that deg(A)=3, B is an odd vertex,
deg(C)=2 and D& E are adjacent.
Part-B (5*16=80)
11.a) i) How many bit strings of length 10 contain (i) Exactly 4 1’s (a)(ii) State and prove handshaking theorem. If all the vertices of an undirected
(ii) At most 4 1’s (iii) At least 4 1’s (iv) An equal number of 0’s and 1’s graph are each of degree k, show that the number of edges of the graph
ii) Using induction principle, prove that n  2n is divisible by3. is a multiple of k.
3

OR OR
15.(b)(i) Prove that the number of vertices of odd degree is even.
b) i) Using generating function, Solve an  3 an  1 = 2 ,  n  1, a0 = 2.
ii) A total of 1232 students have taken course in Spanish, 879 have taken a course in (b)(ii) Show that complete graph on n vertices 𝑘𝑛 with 𝑛 ≥ 3 has Hamilton
French, and 114 have taken a course in Russian. Further, 103 have taken course in cycle. Obtain all the two edge disjoint Hamilton cycles in 𝑘7 .
both Spanish and French, 23 have taken courses in both French and Russian, and
14 have taken at least one of Spanish, French, and Russian, how many students
have taken a course in all three language.
12.a) i)Using method of generating function, solve an = 4 an  1 ,  n  1 , a0 = 2.
ii) A cricket club consists of 15 members of whom 7 are bowlers. In how many
ways can a team of eleven be chosen so as to include at least 5 bowlers.
OR
b)i)Solve the recurrence relation an  5 an  1 + 6 an + 1 = 4n , n  2 .
ii) Find the number of integers between 1 and 250 both inclusive that are not
divisible by 2, 3,5.
13.a) i) In a survey of 120 passengers, an airline found that 52 enjoyed meals,75
Enjoyed drinks,62 enjoyed tea.35 enjoyed any given pair of these
Beverages and 20 enjoyed all of them. Find number of passengers
who enjoyed only tea, only one of the three, exactly 2 of the 3
beverages, None of the drinks.
ii) Solve the recurrence relation an  2 an  1 = 2n ,given that a0 = 2.
b) i) prove that maximum number of edges is a connected graph with n vertices is
n( n  1) DEPARTMENT OF COMPUTER SCIENCE ANDENGINEERING
CAT II: SEP 2018
2
 MA8351-DISCRETE MATHEMATICS a)ii) Examine whether the following pairs of graphs G1 and G2 given in
Year/Sem : II/III Date : 02.08.2018 figures are isomorphic or not
Class/Section : II CSE A and B Duration : 3 Hours
Faculty : M.TAMIL MOZHI Max. Marks : 100

Answer ALL Questions

Part – A (10*2=20)
1. How many permutations are there in the word MALAYALAM?
Find the recurrence relation of the sequence s(n)  a : n  1 . OR
n
2.
b)i) Prove that a connected graph G is Euler graph if and only if every vertex of
3. Write the generating function for the sequence 1,a,a2,a3,a4,…. G is of even degree
4. Solve 𝑎𝑘 = 3𝑎𝑘−1 for 𝑘 ≥ 1 with𝑎0 = 2. ii) State and prove hand shaking theorem. Also prove that maximum number of edges is
5. How many permutations of {a,b,c,d,e,f,g} end with a? n( n  1)
6. Draw the complete graph K5. a connected graph with n vertices is .
7. Show that Kn has a Hamilton circuit when n≥3. 2
8. Show that C6 is bipartite graph. 14. a)i) Using the method of generating function, solve the recurrence relation
9. Give an example of an Euler graph. sn  3sn1  4sn2  0; n  2 Given that s 0  3 and s1  2
10. Define complete bipartite graph.
ii) Prove by mathematical induction that 3  7  2 is divisible by 8 for
n n
Part-B (5*16=80)
11.a)i) Find the number of integers between 1 and 500 that are not divisible by each positive integer n.
any of the integers 2,3,5 and 7. OR
ii) From a club consisting of six men and seven women, in how many b)i) Solve the recurrence relation of the Fibonacci sequence of numbers.
ways we select a committee of (i) 3 men and four women? (ii) 4 person ii) If G is connected simple graph with n vertices with n ≥ 3, such that
which has atleast one women? (iii) 4 person that atmost one man? n
(iv) 4 person that has children of both sexes. the degree of every vertex in G is at least , then prove that G has Hamiltoncycle.
OR 2
15.a)i) Prove that the number of odd degree vertices in any graph is even.
b)(i) Solve G (k )  7G (k  1)  10G (k  2)  8k  6, fork  2
ii) Let G be a graph with exactly two vertices has odd degree, then prove that
. (ii) Prove that a simple graph with n vertices must be connected if it has there is a path between those two vertices.
more than (n-1)(n-2)/2 edges OR
12.a )i) If 𝑛 Pigeon hole are occupied by (𝑘𝑛 + 1)pigeons, where 𝑘 is positive integer, b)i) If all the vertices of an undirected graph are each of degree k, show that the
prove that atleast one pigeon hole is occupied by 𝑘 + 1 or more pigeons . Hence, find number of edges of the graph is a multiple of k.
the minimum number of 𝑚 integers to be selected from 𝑆 = {1,2, … . . ,9} so that the
ii) Give an example of a graph which is (a) Eulerian but not Hamiltonian
sum of two of the 𝑚 integers are even.
(b)Hamiltonian but not Eulerian (c) Eulerian and Hamiltonian
(d) Neither Hamiltonian nor Eulerian.
1 1 1
(ii) Prove that   ...   n for n  2 using principle of mathematical
1 2 n
induction. OR
b)i) Solve the recurrence relation an  7an1  6an2  0, for n  2 with initial
conditions a0  8 and a1  6 ,using generating function.

3n 1  1
r 0 3r 
n
b)(ii) Using mathematical induction show that .
2
mathematical induction.
13. a)i) Prove that the maximum number of edges in a simple disconnected
(n  k )( n  k  1) DEPARTMENT OF COMPUTER SCIENCE ANDENGINEERING
graph G with n vertices and k components is CAT II: SEP 2018
2 MA6566-DISCRETE MATHEMATICS
 Year/Sem : III/V Date : .09.2018 (𝑛−𝑘)(𝑛−𝑘+1)
Class/Section : III CSE A Duration : 3 Hours cannot have more than edges
2
Faculty : M.BIMI Max. Marks : 100
Answer ALL Questions (ii)State and prove Handshaking theorem Also prove that maximum number of edges is a
Part – A (10*2=20)
1. How many different words are there in the word ENGINEERING ? n( n  1)
connected graph with n vertices is .
2. Find the minimum number of students need to guarantee that five of them 2
belongs to the same subject, if there are five different major subjects. 14.a)(i)Determine which of the following graph are bipartite or not . If a graph is bipartite, state if
3. Find the generating function of the sequence 2,2 2,23,24,…….. it is completely bipartite.
4. How many 3 digit even numbers formed with the digits 1,2,3,4,5.
5. Using generating function, solve an = 4an  1 ,  n  1 , a0 = 2.
6. Define pseudo graph
7. What are the necessary conditions for G1 and G2 to be isomorphic.
8. Define Graph.
9. Define complete graph. (ii)Prove that a connected graph G is Eulerian if only if all the vertices are of even degree
10. How many edges are there in a graph with 10 vertices each of degree six OR
Part-B (5*16=80) b) i) Define Euler graph and Hamiltonian graph. Give an example of (1)a graph which is
11. a) i) Using mathematical induction prove that Hamiltonian but not Eulerian, (2) a graph which is Eulerian but not Hamiltonian, (3)a graph which
is neither Eulerian nor Hamiltonian.
n(n  1)( 2n  1)

2
n
i 1
i
 ii)Prove that a simple graph with n vertices must be connected if
6 (n  1)( n  2)
it has more than edges.
3  5x 2
ii) Using generating function solve OR
(1  2 x  3x 2 ) 15 a) i)Draw the complete bipartite graph K 2,3 , K 3'3 , K 3,5 , K 2, 6
b) i) Using generating function solve an+2 -5an+1 + 6an = 0, a0=0, a1=1 ii) using circuits examine whether the following pair of graph given below are isomorphic or
ii) Using mathematical induction prove that 12+32+52…….+ (2n-1)2 = not
n(2n  1)( 2n  1)
3
12 a) i) Using recurrence relation solve an -6an-1 +8an-2 = 3n for n  2 where
a0 = 3, a1 = 7
ii) Solve the recurrence relation s(n) – 7s(n-1) +6s(n-2) = 0 given s(0) =8,
OR
s(1) = 6 OR
b) i) In a survey of 120 passengers, an airline found that 52 enjoyed
b) i)Show that complete graph on n vertices 𝑘𝑛 with 𝑛 ≥ 3 has Hamilton
meals,75 enjoyed drinks,62 enjoyed tea.35 enjoyed any given pair of these
cycle. Obtain all the two edge disjoint Hamilton cycles in 𝑘7
beverages and 20 enjoyed all of them. Find number of passengers who
enjoyed only tea, only one of the three, exactly 2 of the 3 beverages’ ,None ii) If G is connected simple graph with n vertices with n ≥ 3, such that
of the drinks. n
the degree of every vertex in G is at least , then prove that G has Hamilton cycle
ii)Solve the recurrence relation an  2 an  1 = 2n ,given that a0 = 2. 2
13.a)(i) Determine whether the following graphs G and H are isomorphic.
Give reason.

DEPARTMENT OF COMPUTER SCIENCE ANDENGINEERING

CAT II: SEP 2018
(ii)Explain Konigsberg bridge problem OR MA8351-DISCRETE MATHEMATICS
b) (i) Prove that a simple graph with n vertices and k components Year/Sem : III/V Date : .09.2018
Class/Section : III CSE B Duration : 3 Hours
 Faculty : M.LAKSHMI PRIYA Max. Marks : 100
n( n  1)
b) i) prove that maximum number of edges is a connected graph with n vertices is
Answer ALL Questions
Part – A (10*2=20)
2
1. State the pigeonhole principle. ii) Define graph isomorphism and give an example of isomorphic and non-
2. How many permutations are there in the word M I S S I S S I P P I? isomorphic graphs.
3. Find the generating function of the sequence 2,2 2,23,24,…….. 14.(a)(i)Show that if G is a simple graph with n vertices and K components, then the number
4. How many 3 digit even numbers formed with the digits 1,2,3,4,5. of edges is at most ( n  k ) ( n  k + 1 ) / 2.
5. Using generating function, solve an = 4an  1 ,  n  1 , a0 = 2. (a)(ii) Using the method of generating function, solve the recurrence relation
6. Draw the complete graph K5. sn  3sn1  4s n2  0; n  2 Given that s 0  3 and s1  2
7. Show that Kn has a Hamilton circuit when n≥3.
OR
8. Show that C6 is bipartite graph. .(b)(i)Define Euler graph and Hamiltonian graph. Give an example of (1)a graph which is
9. Give an example of an Euler graph. Hamiltonian but not Eulerian, (2) a graph which is Eulerian but not Hamiltonian,
10. How many edges are there in a graph with 10 vertices each of degree six (3)a graph which is neither Eulerian nor Hamiltonian.
Part-B (5*16=80) ii) using circuits examine whether the following pair of graph given below are isomorphic or
11. a) i) Using mathematical induction prove that not
n(n  1)( 2n  1)

2
n
i 1
i

6
3  5x
ii) Using generating function solve OR
(1  2 x  3x 2 )
b) i) Using generating function solve an+2 -5an+1 + 6an = 0, a0=0, a1=1
ii) Solve the recurrence relation an  2 an  1 = 2n ,given that a0 = 2. 15 a) i) Prove that a simple graph with n vertices must be connected if
(n  1)( n  2)
12.a) i)Using method of generating function, solve an = 4 an  1 ,  n  1 , a0 = 2. it has more than edges
ii) A cricket club consists of 15 members of whom 7 are bowlers. In how many 2
ways can a team of eleven be chosen so as to include at least 5 bowlers. ii)State and prove Handshaking theorem Also prove that maximum number of edges is a
OR n( n  1)
b) i)Solve the recurrence relation an  5 an  1 + 6 an + 1 = 4n , n  2 . connected graph with n vertices is . OR
ii) Find the number of integers between 1 and 250 both inclusive that are not
2
divisible by 2, 3,5. b)i) Prove that the number of odd degree vertices in any graph is even.
13.a)(i) Determine whether the following graphs G and H are isomorphic. ii) Let G be a graph with exactly two vertices has odd degree, then prove that
Give reason. there is a path between those two vertices.

ii) Examine whether the following pairs of graphs G1 and G2 given in

figures are isomorphic or not

OR