Consider graphs in which there is at most one edge between any two vertices. Use
ID: 3885539 • Letter: C
Question
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 n^2 edges. Use proof by contradiction to show that the set of all prime numbers is infinite. Find grammars for sigma = {a, b} that generate the sets of a) All strings with exactly two a's b) All strings with at least three a's. The reverse of a string can be defined by the recursive rules a^R = a: (wa)^R = aw^R: for all a elementof sigma, w elementof sigma*. Prove that a) (uv)^R = v^R u^R, for all u, v elementof sigma^+. b) (w^R)^R = w for al w elementof sigma. Show that a) The grammars S rightarrow aSb|ab|lambda and S rightarrow aaSbb|aSb|ab|lambda are equivalent. b) The grammars S rightarrow aSb|bSa|SS|a and S rightarrow aSb|bSa|a are not equivalent.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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.