Answer to Question #173511 in Discrete Mathematics for ANJU JAYACHANDRAN

Question

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.

Answer 1

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.