?

?

2. Proof by contradiction (a) Given a graph G, define k(G) to be the greatest possible natural number n such that Kn (the complete graph on n vertices) is a subgraph of G. Recall that the chromatic number x(G) of G is the smallest possible number of colours sufficient to color the vertices of G so that no two adjacent vertices receive the same color (see Assignment 3 Question 3). Prove that x(G) 2 k(G). (b) Let x, y, z be three integer numbers. Prove that if x + y = z, then is even or y is even. (c) Consider a correct claim with its incorrect proof. Claim: Consider the equation x+y-3 = 0. A pair (xo, yo) is called a rational solution of x + y - 3 = 0 if xo and yo are rational; x+y-3=0 The equation x + y - 3 = 0 has no rational solutions. Proof. Assume that it is not true that x + y - 3 = 0 has no rational solutions. That is, every solution (x, y) of x + y-3 = 0 is rational. Consider one of these solutions, say (a, b), then a and b are rational; a + b-3=0 Since a, b are rational there are integer numbers Pa, Pb, das 9b 9a 0,96 0 such that Pa and b = Pb. Then a= qa 9b 2 Pa Pb qa 9b r g +phi g 99 + 2 = 3 3 pq + piq Because 99 q2 is a factor of paq + pq2. Because qa and pa have no common divisors the only way pq+pq can be a multiple of qa if q? is a multiple of q2. Therefore q, is a multiple of 9. So there is an integer k, such that q = = kqa- is equal to an integer paa+piq should be a multiple of q2q. Hence qis also a factor of paq + pq2. Because q, and p, have no common divisors the only way pa+pq can be a multiple of q? if qa is a multiple of q. Therefore q, is a multiple of qa. So there is an integer t, such that qa = tqa. = Now qatqa and qb= kqa. It is not possible. Therefore our assumption was incorrect and x + y-3= 0 has no rational solutions. Find ALL logical mistakes in the proof. You do not need to prove this claim.