Graph Coloring Problem

Please use words to describe the solution process: Let G be a graph with n vertices that is not a complete graph. Prove that x (G) < n HINT: If G does not contain k3 as a subgraph, then every face must have degree at least 4. *(Please see attachment for proper symbols)

Graph Coloring Problem

Please use words to describe the solution process: Let G be a graph with exactly one cycle. Prove that x(G) is less than or equal t0 3. *(Please see attachment for proper symbols)

Propositional Logic : DeMorgan's Laws and Truth Tables

Please see the attached file for the fully formatted problems. Verify DeMorgan's laws (equation 1 and 2 below) using truth tables. Prove the generalized DeMorgan’s laws: (1) (NOT(p1 p2 .... pk)) (2) (NOT(p1+p2+...+pk)) by induction on k, using the basic laws: NOT(pq) NOT(p+q) Then, justify the generalized laws informally by describing what 2k row truth tables for each expression and their subexpressions look like.

Propositional Logic : Commutitivity of Sums and Products

Please see the attached file for the fully formatted problems. Prove that: p1+p2+...+pn is equivalent to the sum (logical OR) of the pi’s in any order. and p1p2 ... pn is equivalent to the product (logical AND) of the pi’s in any order.

Discrete Structures : Coloring

Let G be a properly colored graph and let us suppose that one of the colours used is red. The set of all red-coloured vertices have a special property. What is it? Graph colouring can be thought of as partitioning V(G) into subsets with this special property. (See attachment for full background)