Assignment 1(1)-1.docx [Read-Only] [Compatibility Mode] - Word inin magdalen -0
ID: 3195778 • Letter: A
Question
Assignment 1(1)-1.docx [Read-Only] [Compatibility Mode] - Word inin magdalen -0 × File Home Insert Design Layout References Mailings Review View Help Tell me what you want to do Share Help Contact Show What's Support Training Help & Support New 1. Consider graphs in which there is at most one edge between any two vertices. Use proof by induction to show that under this condition a graph with n vertices has at most n2 edges. Use proof by contradiction to show that the set of all prime numbers is infinite Find grammars for = { a, b, that generate the sets of 2. 3. a) All strings with exactly two a's. b) All strings with at least three a's. 4. The reverse of a string can be defined by the recursive rules aR = a: for all a E , w E .. Prove that ENG 10-54 AM b) (MO R = 14° for all w E 2/12/2018 Page 1 of 2 266 words English (United States) 120%Explanation / Answer
1) There is atmost 1 edge between 2 vertices.
Graph with 1 vertex will have 0 edges.
Graph with 2 vertices will have 1 edge.
Graph with 3 vertices A,B,C will have (3C2) 3 edges namely AB,BC,AC.
Graph with 4 vertices A,B,C,D will have (4C2) 6 edges namely AB,AC,AD,BC,BD,CD.
P(k)=Let us cosider a graph with k edges
it will have
No of edges= kC2 = k!/( 2! (k-2)!) = k(k-1) /2
Assuming P(k) to be true, we are to provr P(k+1) is true
P(k+1)=Consider a graph with k+1 edges
No of edges= kC2 + k
=(k(k-1)/2 )+ k
=k((k-1)+2)/2 =
=k(k+1)/2
=k+1C2
Hence P(n) is true.
Graph with n vertices will have nC2 edges
=> No of edges = nC2
= n(n+1)/2
= n2/2+ n/2
= O(n2)
This implies graph with n vertices has atmost n2 edges
2) Assume that prime numbers are finite and this list is P1,P2,P3............Pn
Now Consider a number Q
Q= (P1*P2*P3*....*Pn-1*Pn) +1
if Q is not a prime number than any of the prime numbers from the list above will divide it completely.
But none of the Primes divide it completely we still have remainder 1 left, this means Q is prime.
And the list of prime number goes on forever. Hence Prime Number list is infinite.
Please ask rest questions again