1. Which of the following statements are true and which are false? Give reasons for your answer. (20) i) ‘x 2 +y 2 −3 is not dividible by 4.’ is mathematical statement. ii) The number of onto functions from {1,2,3,4,5,6} to {a,b, c,d} is 4!S 4 6 . iii) The generating function associated with a sequence can never be a polynomial. iv) K4,4 is non-planar. v) Every bipartite graph with odd number of vertices is non-hamiltonian. vi) an = an 2 +n,a1 = 0, where n is a power of 2, is a linear recurrence relation. vii) The generating function of the sequence {1,2,3,4,...,n...} is (1−z) −2 . viii) If g(x) is the generating function for {an}n≥1, then (1−x)g(x) is the generating function for the sequence {bn}n≥1 where bn = an −1,∀n. ix) If a graph is isomorphic to its complement, then it has odd number of vertices. x) Every 3-colourable graph is 4-colourable.

i) true

the given statement is mathematical statement: a sentence which is either true or false. It may contain words and symbols.

ii) false

the number of onto functions: $S(6,4)/4!$

where $S(6,4)=4^6-\begin{pmatrix} 4 \\ 1 \end{pmatrix}\cdot3^6+\begin{pmatrix} 4 \\ 2 \end{pmatrix}\cdot2^6-\begin{pmatrix} 4 \\ 3 \end{pmatrix}$

iii) false

for example, polynomial sequences of binomial type are generated by

$\sum\frac{p_n(x)}{n!}t^n$ , where $p_n(x)$ is a sequence of polynomials

iv) false

A complete bipartite graph $K_{mn}$ is planar if and only if $m<3$ or $n>3$

v) true

Let graph G be a bipartite graph with an odd number of vertices and G be Hamiltonian, meaning that there is a directed cycle that includes every vertex of G. As such, there exists a cycle in G would of odd length. However, a graph G is bipartite if and only if every cycle of G has even length. Proven by contradiction, if G is a bipartite graph with an odd number of vertices, then G is non-Hamiltonian.

vi) false

$a_n=a_n^2+n$ is not a linear recurrence relation. Linear recurrence: each term of a sequence is a linear function of earlier terms in the sequence.

vii) false

the generating function of the sequence: $\sum nt^n$

viii) false

$g(x)=\sum a_nx^n$

$(1-x)g(x)=\sum a_nx^n-\sum a_nx^{n+1}$

$b_n=a_n-a_{n-1}$

ix) false

$n(n-1)$ ($n$ is number of vertices) must be divisible by 4. So, If a graph is isomorphic to its complement, then it can have even number of vertices (for example, $n=4$ ).

x) true

A graph having chromatic number $\chi(G)\leq k$ is called a -colorable graph. So, 3-colourable graph has $\chi(G)\leq 3$ , and this means that it has $\chi(G)\leq 4$ also. That is, every 3-colourable graph is 4-colourable.