? ? 2. Proof by contradiction (a) Given a graph G, define k(G) to be the greatest

?

?

Transcribed Image Text:

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ả 9²9² + 2 = 3 3 p²q² + piq² Because 9²9 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. 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ả 9²9² + 2 = 3 3 p²q² + piq² Because 9²9 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.

Answer rating: 100% (QA)

2 a Assume the contrary XG K G Let us call n KG and m ... View the full answer