If K_m,n for m, n ≥ 2 is Hamiltonian, how are m and n related? Justify your answer.

Find a recurrence relation for a_n, the number of ways to arrange cars in a row with n spaces if we can use Maruti 800, Tata Safari or Scorpio. A Tata Safari or Scorpio requires two spaces, whereas a Maruti 800 requires just one space. Assume that you have unlimited number of each type of car and we do not distinguish between 2 cars of the same type.

Express x⁵ in terms of falling factorials and hence evaluate for m = 0,1,2,3,4,5.

write down and count all the partitions of the number 7. To verify your answer use the generating function for P, taking n =7 in Theorem 5 (of Unit 5, Block2).

In the June, 2021 Term-End Examination of MTE-13, it was asked to give a direct and an indirect proof of the following statement.

"If a,b ∈ Z such that a is even and a+b is even, then b is even."

One student gave an indirect proof as follows:

"Let b be m+1, which is an odd number. We already know a and a+b are even. If we substitute b=m+1 in a + b, it becomes a+m+1, which is an odd number. This contradicts the given statement. Hence b is an even number."

What is wrong with the above proof? Also give a correct direct and an indirect proof.

What do you understand by a subdivision of a graph? Is every subdivision of a Hamiltonian graph Hamiltonian? Justify.

Is the complement of the Peterson graph planar? Justify your answer.

Draw three nonisomorphic induced subgraphs of the following graph, each having the same number of vertices. Justify your choice.

For any statements p,q and r, prove that

List all the onto mappings from the set {a,b,c,d} to {1,2,3,4}. How many onto mappings are there form {a,b,c,d} to {1,2,3,4,5}?

Solve the recurrence relation:

There are about 77 crore ways to arrange the letters of the word “COMBINATORICS”. Count the exact number of such ways.

Using generating functions find 

Express the following statements in symbolic form.

i) There is a man in the park with blue eyes.

ii) Every blue-eyed man in the park is wearing a red hat.

iii) If a man wears no hat, then he has black eyes.

Draw the logic circuit for the Boolean expression

Check whether the following statements are true or not. Justify your answers with a short proof or a counter example.

i) If the contrapositive of a statement is true, then the statement itself is also true.

ii) a_n+3a_n-1+2a_n-2= 2" is a linear homogeneous recurrence relation.

iii) A particular solution of the recurrence relation a_n-2a_n-1 + a_n-2=1 has the form Cn².

iv) There exists a boolean expression in variables x,x, and x, with CNF as

v) If a dice is rolled thrice, then the probability of getting a 6 each time is 

vi) Every odd cycle has the same chromatic and edge chromatic numbers.

vii) Every Eulerian graph is Hamiltonian.

viii) gives the number of ways in which any 3 objects can be placed in any 4 boxes.

ix) There exists a self-complementary planar graph on 5 or more vertices.

x) The number of partitions of 6 is 10.

नीचे दी हुई तालिका में परिभाषित करन के लिए खूनीयाव्यांजक ज्ञात कीजिए।

क्या 7 सीधी पर कोई 4-नियमित साफ है अपने उत्तम की पुष्टि कीजिए। 

0 से 759 तक की संख्या में से किसी संसाली या से विभाजन नहीं है? 

क) पुनरावृ‌नित संबंध

की जनक फना विधि से हम कीजिए। साथ ही अपनी उन्तार से जात कीजिए।

किसी ग्राफ G के लिए शीर्ष-संबद्वतांक और काट शीर्ष समुच्चय परिभाषित कीजिए। नीचे दिए गए ग्राफ

के लिए शीर्ष - संबद्वतांक और काट शीर्ष समुच्चय ज्ञात कीजिए।