Question

For the following statements (taken from various theorems in the book know what the words mean to do these exercises): note it is not necessary to (i) translate into symbols (using V or 3 if the statement is implicitly quantified and choosing an appropriate domain). You may write out your predicates in place. (See example from class.) (ii) Write the negation of the statement in words (you may find it easier to negate the symbolic statement first) (iii) write the contrapositive of the original statement in words (1) For all functions f:S + T, if f:S T is onto, then 1 for alls ES there exists att such that f($) = t. for all t ET there exists an s ES such that f(s) = t. (2) For all graphs G, if G is finite and connected, then G has a spanning tree. (3) If G is a finite connected graph and every vertex has even degree, then G is Eulerian. (4) For all graphs G with no loops or parallel edges, if |VG)] = n > 3 and deg(v) > n/2 for each vertex of G, then G is Hamiltonian. (Note the domain here is {graphs with no loops or parallel edges}.)

Answer 1

1 "For all functions f: S T for all t ET there exists , if f: S an ses T is onto, then such that f(s)= t. (i) ufis T, is of is onto thin VtET I DES: f(= t. (1) of af: S T such that it is NOT onto, then I t ET such that VSES f(s) ² t. In words: If there exists a function fos T which is NOT onto then there bxists a tET such that for every SES f18 t . (iii) Contrapositiu of original statement: If there exerts tET such that for all ses f (8) + t, then there exists fisT which is NOT onto . 2 "Too all graphs G, if G is finite and connected, then G has a spanning tree." (i) V graphs G such that is finite and connected, G has a spanning tre. G is NOT finite of NOT Connected (ii) of there exists a graph such that then G has no spanning tru. (Fil) of G has no spanning tree, then such that either G is NOT finite go there exists graph G. oo NOT connected.

I 3 "If G is a finite connected graph and every vertex has even degru then in Euclidean. " (i) of G is a finite connected graph such that I vertex has even degree then G is Euclidean. (1) If G is NOT finite conned graph or there exists a wertex which even degree has NOT than G is NOT Euclidean. (ii) Of G is NOT Euclidean, then either is NOT finite connected graph or there exists a vertex whose degru is NOT even. A " For all graphs G with no loops or parallel edges, if IV (Gll-n23 degree (v) a n for each vertex of 6 , then G is Hamiltonian. and (1) VG with no loops or parallel edges, if N(Gil = n33 and deg (0)3 n vo of G, then G is Hamiltonian. there exists (ii) f G with loops and parallel idges with lucalle and or deg (vi <h then G is NOT Hamiltonian. there exists (1) Of G is NOT Haniltonian then there exists with loops. and parallel edges with lucall <3 or there exests, vertex & such that degru (v) <f.