Solution to 1. Which of the following statements are true and which are false? Give reasons for … - Sikademy
Author Image

Archangel Macsika

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.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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}


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.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3275-qpid-1974