Discrete Math: Logic Problems, Truth Table and Rules of Inference

Please see the attached file for the fully formatted problems. 1. Construct the truth table for the compound proposition: [p (q r)] (r p) p q r ------------------------------------------------------------- T T T T T F T F T T ...continues

Graphs and Digraphs : Edge-Connectivity

If G is a graph of order n>=2 such that for all distinct nonadjacent vertices u and v, d(u)+d(v)>=n-1, then the edge-connectivity k1(G)=Deta(G), where Deta(G) is the least degree of G.

Discrete Math: Logic and Directed Graphs

Please see the attached file for the fully formatted problems. 1. Circle T for True or F for False as they apply to the following statements: T F Every compound is either a tautology or a contradiction. T F Integers are Rational. T F The empty set has no subsets. T F Onto functions map smaller sets to bigger sets. T F ...continues

Problems - Discrete

1. For the function f:{1, 2, 3, 4, 5} {1, 2, 3, 4, 5} defined as: f = {(1,4), (2,5), (3,1), (4,2), (5,3)}, (a) find f 1; (b) find f o f o f o f o f . 2. Which of the strings,11111111, 00000000, 10010110, or 00001011, is closest in Hamming distance to 01101001? 3. Find the polynomial big-O estima ...continues

Planar Graph

Prove that the complete graph K5 is nonplanar.

Recurrence Relations

I need to solve the following recurrence relation: (please see the attached file).

Prove that n-Cube Qn is not planar for n>=4.

I need to prove the n-cube Qn is not planar for n greater than or equal to 4.

planar graph vertex degree at most 5

I need to show that if G is a planar graph, then G must have a vertex of degree at most 5.

Discrete Math: Logic

Please see the attached file for the fully formatted problems. Discrete Math True or False questions 1. Circle T if the corresponding statement is True or F if it is False. T F The Fibonacci Sequence is {sn | sn = sn1 + sn2, with s0 = 1 and s1 = 1}. T F The First (Weak) and Second (Strong) Principles of M ...continues

Equivalence Relations

Verify that each of the following are equivalence relations on the plane R^2 (where R are real numbers) and describe the equivalence classes geometrically. 1) (x1,y1)R(x2,y2) if and only if x1 = x2 2) (x1,y1)R(x2,y2) if and only if x1 + y1 = x2+y2 3) (x1,y1)R(x2,y2) if and only if x1^2 + y1^2 = x2^2 + y2^2